F - Everywhere is Sparser than Whole (Judge) Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

頂点集合が空でない単純無向グラフの密度を \displaystyle\frac{(辺数)}{(頂点数)} と定義します．

正整数 N, D と，N 頂点 DN 辺の単純無向グラフ G が与えられます． G の頂点には 1 から N までの番号が付いており，i 番目の辺は頂点 A_i と頂点 B_i を結んでいます． G が以下の条件を満たしているかどうかを判定してください．

条件: G の頂点集合を V とする． V の任意の空でない真部分集合 X に対して，X による G の誘導部分グラフの密度は D 未満である．

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

誘導部分グラフとは

グラフ G の頂点部分集合 X に対して，X による G の誘導部分グラフとは，「頂点集合が X であり，辺集合が『 G の辺であって X 内の 2 頂点を結ぶもの全体』であるグラフ」を指します． 上記の条件では，頂点部分集合として空集合でも全体でもないもののみを考えていることに注意してください．

制約

  • T \geq 1
  • N \geq 1
  • D \geq 1
  • 1 つの入力に含まれるテストケースについて，DN の総和は 5 \times 10^4 以下である．
  • 1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq DN)
  • (A_i, B_i) \neq (A_j, B_j) \ \ (1 \leq i < j \leq DN)

入力

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

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

各テストケース \mathrm{case}_i \ (1 \leq i \leq T) は以下の形式である．

N D
A_1 B_1
A_2 B_2
\vdots
A_{DN} B_{DN}

出力

T 行出力せよ． i 行目には，i 番目のテストケースについて，与えられたグラフ G が条件を満たすなら Yes を，満たさないなら No を出力せよ．

入力例 1

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

出力例 1

Yes
No
  • 1 つ目のテストケースは問題 D の出力例 1 と同じであり，条件を満たします．
  • 2 つ目のテストケースについて，頂点集合 \{1, 2, 3, 4\} の空でない真部分集合 \{1, 2, 3\} による誘導部分グラフの辺集合は \{(1, 2), (1, 3), (2, 3)\} であり，その密度は \displaystyle\frac{3}{3} = 1 = D です． したがって，このグラフは条件を満たしません．

Score : 900 points

Problem Statement

We define the density of a non-empty simple undirected graph as \displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}.

You are given positive integers N, D, and a simple undirected graph G with N vertices and DN edges. The vertices of G are numbered from 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Determine whether G satisfies the following condition.

Condition: Let V be the vertex set of G. For any non-empty proper subset X of V, the density of the induced subgraph of G by X is strictly less than D.

There are T test cases to solve.

What is an induced subgraph?

For a vertex subset X of graph G, the induced subgraph of G by X is the graph with vertex set X and edge set containing all edges of G that connect two vertices in X. In the above condition, note that we only consider vertex subsets that are neither empty nor the entire set.

Constraints

  • T \geq 1
  • N \geq 1
  • D \geq 1
  • The sum of DN over the test cases in each input file is at most 5 \times 10^4.
  • 1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq DN)
  • (A_i, B_i) \neq (A_j, B_j) \ \ (1 \leq i < j \leq DN)

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 \mathrm{case}_i \ (1 \leq i \leq T) is in the following format:

N D
A_1 B_1
A_2 B_2
\vdots
A_{DN} B_{DN}

Output

Print T lines. The i-th line should contain Yes if the given graph G for the i-th test case satisfies the condition, and No otherwise.

Sample Input 1

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

Sample Output 1

Yes
No
  • The first test case is the same as Sample Input 1 in Problem D, and it satisfies the condition.
  • For the second test case, the edge set of the induced subgraph by the non-empty proper subset \{1, 2, 3\} of the vertex set \{1, 2, 3, 4\} is \{(1, 2), (1, 3), (2, 3)\}, and its density is \displaystyle\frac{3}{3} = 1 = D. Therefore, this graph does not satisfy the condition.