分数: 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