C - Orientable as Desired 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1100 点

問題文

頂点に 1,2,\dots,N の番号が付いた N 頂点 M 辺の単純連結無向グラフ G があります。 i 番目の辺は 2 つの頂点 u_i,v_i を結んでいます。

以下の条件をすべて満たす長さ N の非負整数列 X=(X_1,X_2,\dots,X_N) が存在するか判定してください。

  • 各 v=1,2,\dots,N に対し、 X_v は G における頂点 v の次数を超えない
  • G の M 本の辺を向き付けることで得られる有向グラフであって、各 v=1,2,\dots,N に対し、頂点 v の入次数・出次数のいずれかが X_v に等しいようなものが存在しない

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

制約

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • N-1 \leq M \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • 入力される値はすべて整数
  • 入力で与えられるグラフ G は単純連結無向グラフ
  • 1 つの入力に含まれるテストケースについて、 N の総和は 2 \times 10^5 以下
  • 1 つの入力に含まれるテストケースについて、 M の総和は 2 \times 10^5 以下

入力

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

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

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

T 行出力せよ。i 行目には i 番目のテストケースについて、条件をすべて満たす X が存在する場合は Yes を、存在しない場合は No を出力せよ。

入力例 1

3
4 4
1 2
2 3
3 4
4 1
7 6
3 4
3 6
2 5
1 2
1 3
2 7
15 20
11 13
11 7
12 6
5 2
4 1
15 3
9 8
13 5
8 6
7 5
11 8
12 9
14 1
1 11
6 7
1 3
2 3
3 7
5 12
10 6

出力例 1

Yes
No
Yes

1 番目のテストケースについて、たとえば X=(2,2,2,1) が条件を満たします。

2 番目のテストケースについて、条件を満たす X は存在しません。

Score : 1100 points

Problem Statement

There is a simple connected undirected graph G with N vertices and M edges, where the vertices are labeled 1,2,\dots,N. The i-th edge connects two vertices u_i and v_i.

Determine whether there exists a length-N sequence of non-negative integers X=(X_1,X_2,\dots,X_N) that satisfies all of the following conditions:

  • X_v does not exceed the degree of vertex v in G for each v=1,2,\dots,N.
  • There is no directed graph obtained by assigning directions to the M edges of G in which, for each v=1,2,\dots,N, either the in-degree or the out-degree of v equals X_v.

You have T test cases; solve each of them.

Constraints

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • N-1 \leq M \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • All input values are integers.
  • The graph G given in the input is a simple connected undirected graph.
  • The sum of N over all test cases in each input is at most 2 \times 10^5.
  • The sum of M over all test cases in each input is at most 2 \times 10^5.

Input

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

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

Each case is given in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print T lines. The i-th line should contain the answer for the i-th test case. If there exists an X that satisfies the conditions, print Yes; otherwise, print No.

Sample Input 1

3
4 4
1 2
2 3
3 4
4 1
7 6
3 4
3 6
2 5
1 2
1 3
2 7
15 20
11 13
11 7
12 6
5 2
4 1
15 3
9 8
13 5
8 6
7 5
11 8
12 9
14 1
1 11
6 7
1 3
2 3
3 7
5 12
10 6

Sample Output 1

Yes
No
Yes

In the first test case, for example, X=(2,2,2,1) satisfies the conditions.

In the second test case, no sequence X satisfies the conditions.