A - Big Clique Everywhere Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

1 から N までの番号がついた N 頂点の単純無向グラフ G が与えられます。 G は M 本の辺を持ち、i 本目の辺は頂点 A_i と B_i を結びます。

G が次の条件を満たすか判定してください。

  • 頂点集合 \{1,2,\cdots,N\} のすべての部分集合 X に対して、X の部分集合 Y であって |Y|\ge \frac{|X|}{2} かつ Y がクリークを形成するものが存在する。

解くべきテストケースは T 個あります。

制約

  • 1\le T \le 10^3
  • 1\le N \le 10^5
  • 0 \le M \le 10^6
  • 1 \le A_i,B_i \le N
  • 与えられるグラフは自己辺も多重辺も含まない。
  • ひとつの入力の中のテストケースすべてにわたる N の総和は 10^5 以下である。
  • ひとつの入力の中のテストケースすべてにわたる M の総和は 10^6 以下である。
  • すべての入力値は整数である。

入力

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

T
case_1
case_2
\vdots
case_T

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

各テストケースについて、G が条件を満たすなら Yes、そうでないなら No と出力せよ。
Yes または No の出力において、各文字は大文字・小文字のいずれでもよい。

入力例 1

4
3 3
1 2
1 3
2 3
3 2
1 2
1 3
3 1
1 2
3 0

出力例 1

Yes
Yes
Yes
No

1 番目のテストケースについて、G は条件を満たします。 この場合、すべての部分集合 X がクリークであるため、単に Y=X とできます。

2 番目のテストケースについて、G は条件を満たします。 例えば、X=\{2,3\} に対しては、Y=\{2\} とできます。

4 番目のテストケースについて、G は条件を満たしません。 X=\{1,2,3\} とすると、条件を満たす X の部分集合 Y はありません。

Score : 600 points

Problem Statement

You are given a simple undirected graph G with N vertices numbered 1 to N. G has M edges and the i-th edge connects vertices A_i and B_i.

Check if G satisfies the following condition:

  • For every subset X of the vertex set \{1,2,\cdots,N\}, there exists a subset Y of X such that |Y|\ge \frac{|X|}{2} and Y forms a clique.

You have T testcases to solve.

Constraints

  • 1\le T \le 10^3
  • 1\le N \le 10^5
  • 0 \le M \le 10^6
  • 1 \le A_i,B_i \le N
  • The given graph doesn't contain self-loops or multiple edges.
  • The sum of N across the test cases in a single input is at most 10^5.
  • The sum of M across the test cases in a single input is at most 10^6.
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

For each test case, if G satisfies the condition, print Yes, and otherwise print No.
In printing Yes or No, you can output each letter in any case (upper or lower).

Sample Input 1

4
3 3
1 2
1 3
2 3
3 2
1 2
1 3
3 1
1 2
3 0

Sample Output 1

Yes
Yes
Yes
No

For the 1-st test case, G satisfies the condition. In this case, every subset X is a clique, so we can just let Y=X.

For the 2-nd test case, G satisfies the condition. For example, for X=\{2,3\}, we can let Y=\{2\}.

For the 4-th test case, G doesn't satisfy the condition. If we let X=\{1,2,3\}, no subset Y of X satisfies the condition.