103455: [Atcoder]ABC345 F - Many Lamps
Description
Score: $550$ points
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
Input
Output
问题描述
有一个简单的图，有N个顶点，编号为1到N，有M条边，编号为1到M。第i条边连接顶点u_i和v_i。
每个顶点上有一个灯。最初，所有的灯都是关着的。
确定是否可以通过执行以下操作0到M次（包括0和M次），使恰好K个灯亮着。
- 选择一条边。设u和v为该边的端点。切换u和v上灯的状态。也就是说，如果灯亮着，就把它关掉，反之亦然。
如果可能使恰好K个灯亮着，打印出实现这种状态的运算序列。
约束
- 1≤N≤2×10^5
- 0≤M≤min(2×10^5，N(N-1)/2)
- 0≤K≤N
- 1≤u_i＜v_i≤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≤X≤M
- 1≤e_i≤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