Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の単純グラフがあります。辺 i は頂点 u_i と頂点 v_i を結んでいます。
各頂点にはランプが 1 個ずつ載っています。はじめ、全てのランプは消えています。
以下の操作を 0 回以上 M 回以下行うことで、ランプがちょうど K 個ついた状態にできるかどうかを判定してください。
- 辺を 1 本選ぶ。辺の両端点を 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 \lt 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 回以上選んでもよいです。)
入力例 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
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