← 返回题目列表

AtCoder · abc345_f

I. 许多灯

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

有一个简单的图表 N 顶点编号 1 to N 和 M 边编号 1 to M。边缘 i 连接顶点 u_i 和 v_i.
每个顶点上都有一盏灯。最初,所有灯都关闭。

判断是否可以精确转动 K 通过执行以下操作来点亮 0 和 M 次,含在内。

  • 选择一条边。让 u 和 v 是边缘的端点。切换灯的状态 u 和 v。也就是说,如果灯亮着,就把它关掉,反之亦然。

如果可以精确转动 K 灯亮起,打印实现此状态的一系列操作。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
  • 0 \leq K \leq N
  • 1 \leq u_i < v_i \leq N
  • 给定的图表很简单。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

输出

如果无法精确转动 K 灯亮,打印 No.
否则,首先打印 Yes,然后按以下格式打印一系列操作:

X
e_1 e_2 \dots e_X

在这里, X 是操作次数,并且 e_i 是在 i-第次操作。这些必须满足以下条件:

  • 0 \leq X \leq M
  • 1 \leq e_i \leq M

如果多个操作序列满足条件,则其中任何一个操作序列都将被视为正确。


示例输入 1

5 5 4
1 2
1 3
2 4
3 5
1 5

示例输出 1

Yes
3
3 4 5

如果我们按照示例输出进行操作,将会如下:

  • 选择边缘 3。打开顶点的灯 2 和顶点 4.
  • 选择边缘 4。打开顶点的灯 3 和顶点 5.
  • 选择边缘 5。打开顶点的灯 1 并关闭顶点上的灯 5.

完成所有操作后,顶点上的灯 1, 2, 3,和 4 已开启。因此,该操作序列满足条件。

满足条件的其他可能的操作序列包括 X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1)。 (允许多次选择同一条边。)


示例输入 2

5 5 5
1 2
1 3
2 4
3 5
1 5

示例输出 2

No

示例输入 3

10 10 6
2 5
2 6
3 5
3 8
4 6
4 8
5 9
6 7
6 10
7 9

示例输出 3

Yes
3
10 9 6