10081: ABC345 —— F - Many Lamps
[Creator : ]
Description
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.
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.
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$
```
```
$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.
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.
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.
- $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.
Sample 1 Input
5 5 4
1 2
1 3
2 4
3 5
1 5
Sample 1 Output
Yes
3
3 4 5
If we operate according to the sample output, it will go as follows:
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.)
- 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.
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 2 Input
5 5 5
1 2
1 3
2 4
3 5
1 5
Sample 2 Output
No
Sample 3 Input
10 10 6
2 5
2 6
3 5
3 8
4 6
4 8
5 9
6 7
6 10
7 9
Sample 3 Output
Yes
3
10 9 6