配点 : $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$ 個のテストケースが与えられるので，それぞれについて答えてください．

制約

• $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 を出力せよ．

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

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$ です． したがって，このグラフは条件を満たしません．