Score: $550$ points

问题陈述

有一个简单图，有 $N$ 个顶点，编号为 $1$ 到 $N$，以及 $M$ 条边，编号为 $1$ 到 $M$。边 $i$ 连接顶点 $u_i$ 和 $v_i$。 每个顶点上都有一盏灯。最初，所有的灯都是关闭的。

确定是否可能通过执行以下操作 $0$ 到 $M$ 次（包括 $M$ 次），打开恰好 $K$ 盏灯。

• 选择一条边。设 $u$ 和 $v$ 是边的端点。切换顶点 $u$ 和 $v$ 上的灯的状态。也就是说，如果灯是开着的，就关闭它，反之亦然。

如果可能打开恰好 $K$ 盏灯，请打印出实现这种状态的操作序列。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a simple graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertices $u_i$ and $v_i$.
Each vertex has one lamp on it. Initially, all the lamps are off.

Determine whether it is possible to turn exactly $K$ lamps on by performing the following operation between $0$ and $M$ times, inclusive.

• Choose one edge. Let $u$ and $v$ be the endpoints of the edge. Toggle the states of the lamps on $u$ and $v$. That is, if the lamp is on, turn it off, and vice versa.

If it is possible to turn exactly $K$ lamps on, print a sequence of operations that achieves this state.

Constraints

• $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$
• The given graph is simple.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $K$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

Output

If it is impossible to turn exactly $K$ lamps on, print No.

Otherwise, first print Yes, and then print a sequence of operations in the following format:

$X$

$e_1$ $e_2$ $\dots$ $e_X$

Here, $X$ is the number of operations, and $e_i$ is the number of the edge chosen in the $i$-th operation. These must satisfy the following:

• $0 \leq X \leq M$

• $1 \leq e_i \leq M$

If multiple sequences of operations satisfy the conditions, any of them will be considered correct.

Sample Input 1

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

Sample Output 1

Yes
3
3 4 5

If we operate according to the sample output, it will go as follows:

• Choose edge $3$. Turn on the lamps on vertex $2$ and vertex $4$.
• Choose edge $4$. Turn on the lamps on vertex $3$ and vertex $5$.
• Choose edge $5$. Turn on the lamp on vertex $1$ and turn off the lamp on vertex $5$.

After completing all operations, the lamps on vertices $1$, $2$, $3$, and $4$ are on. Therefore, this sequence of operations satisfies the conditions.

Other possible sequences of operations that satisfy the conditions include $X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1)$. (It is allowed to choose the same edge more than once.)

Sample Input 2

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

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes
3
10 9 6

update @ 2024/5/16 17:17:10