C - Reverse and DAG Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1000 点

問題文

N 頂点 M 辺の単純有向グラフ G があります．頂点には 1 から N の番号が付いており，i 番目の辺は頂点 a_i から頂点 b_i へ張られています．i\neq j のとき (a_i,b_i)\neq (b_j,a_j) であることが保証されます．また 2 以上 N-2 以下の整数 K が与えられます．

以下の操作を 0 回以上好きな回数行うことで，G を有向閉路を含まないグラフ（DAG）にできるか否かを判定してください．

  • \lbrace 1,\ldots,N\rbrace のサイズ K の部分集合 S を選ぶ．始点と終点の番号がともに S に含まれるような有向辺すべてについて，その向きを反転させる．
    • すなわち，頂点 u から頂点 v\ (u,v\in S) に辺が張られているとき，その辺を削除し，頂点 v から頂点 u への有向辺を追加する．この操作はすべての対象の辺に対して同時に行われる．

T 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

  • 1 \leq T \leq 50000
  • 4 \leq N \leq 2\times 10^5
  • 0 \leq M \leq \min({N(N-1), 2\times 10^5})
  • 2 \leq K \leq N-2
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i
  • i\neq j ならば (a_i, b_i) \neq (a_j, b_j) かつ (a_i,b_i) \neq (b_j,a_j)
  • 一つの入力に含まれる N の総和は 2\times 10^5 以下
  • 一つの入力に含まれる M の総和は 2\times 10^5 以下
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる．

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる．

N M K
a_1 b_1
a_2 b_2
\vdots
a_M b_M

出力

\mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T に対する答えを順に以下の形式で出力せよ．

操作を 0 回以上好きな回数行うことで G を有向閉路を含まないグラフ（DAG）にできるならば Yes ，できないならば No と出力せよ．

入力例 1

3
7 10 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6
7 1
7 19 5
1 4
2 3
2 4
2 5
3 5
3 6
3 7
4 3
4 6
4 7
5 1
5 4
5 6
6 1
6 2
6 7
7 1
7 2
7 5
9 15 5
1 6
2 7
2 9
3 1
3 4
4 5
4 6
4 7
4 8
5 7
5 9
6 5
6 9
7 9
8 9

出力例 1

Yes
No
Yes

1 番目のテストケースでは，以下のように 2 回の操作を行うことで G を有向閉路を含まないグラフにできます．

  • 1 回目の操作では S = \lbrace 1, 2,7 \rbrace として操作を行う． 始点と終点の番号がともに S に含まれるような有向辺は頂点 1 から頂点 2 へ張られた辺と，頂点 7 から頂点 1 へ張られた辺である．これらの辺の向きが反転する．

  • 2 回目の操作では S = \lbrace 4, 5,7 \rbrace として操作を行う． 始点と終点の番号がともに S に含まれるような有向辺は頂点 4 から頂点 5 へ張られた辺である．この辺の向きが反転し，G は有向閉路を含まないグラフになる．

2 番目のテストケースでは，どのように操作を行っても G を有向閉路を含まないグラフにできません．

Score : 1000 points

Problem Statement

There is a simple directed graph G with N vertices and M edges. The vertices are numbered 1 through N, and the i-th edge goes from vertex a_i to vertex b_i. It is guaranteed that (a_i,b_i)\neq (b_j,a_j) for i\neq j. Also, an integer K with 2 \leq K \leq N-2 is given.

Determine whether it is possible to make G a graph with no directed cycles (DAG) by performing the following operation zero or more times.

  • Choose a size-K subset S of \lbrace 1,\ldots,N\rbrace. For every directed edge whose both endpoints' numbers are in S, reverse its direction.
    • That is, if there is an edge from vertex u to vertex v\ (u,v\in S), delete that edge and add a directed edge from vertex v to vertex u. This operation is performed simultaneously for all applicable edges.

T test cases are given; solve each of them.

Constraints

  • 1 \leq T \leq 50000
  • 4 \leq N \leq 2\times 10^5
  • 0 \leq M \leq \min({N(N-1), 2\times 10^5})
  • 2 \leq K \leq N-2
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i
  • (a_i, b_i) \neq (a_j, b_j) and (a_i,b_i) \neq (b_j,a_j) for i\neq j.
  • The sum of N in each input is at most 2\times 10^5.
  • The sum of M in each input is at most 2\times 10^5.
  • All input values are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M K
a_1 b_1
a_2 b_2
\vdots
a_M b_M

Output

Output the answers for \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T in this order in the following format.

Output Yes if it is possible to make G a graph with no directed cycles (DAG) by performing the operation zero or more times, and No otherwise.

Sample Input 1

3
7 10 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6
7 1
7 19 5
1 4
2 3
2 4
2 5
3 5
3 6
3 7
4 3
4 6
4 7
5 1
5 4
5 6
6 1
6 2
6 7
7 1
7 2
7 5
9 15 5
1 6
2 7
2 9
3 1
3 4
4 5
4 6
4 7
4 8
5 7
5 9
6 5
6 9
7 9
8 9

Sample Output 1

Yes
No
Yes

In the first test case, G can be made into a graph with no directed cycles by performing the following two operations.

  • In the first operation, perform the operation with S = \lbrace 1, 2,7 \rbrace. The directed edges whose both endpoints' numbers are in S are the edge from vertex 1 to vertex 2 and the edge from vertex 7 to vertex 1. The directions of these edges are reversed.

  • In the second operation, perform the operation with S = \lbrace 4, 5,7 \rbrace. The directed edge whose both endpoints' numbers are in S is the edge from vertex 4 to vertex 5. The direction of this edge is reversed, and G becomes a graph with no directed cycles.

In the second test case, it is impossible to make G a graph with no directed cycles regardless of the operations performed.