题目描述

頂点集合が空でない単純無向グラフの密度を $\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$ $\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 を出力せよ．

题目大意

给定一张含 $N$ 个点，$DN$ 条边的图 $G=(V,E)$，判断是否满足 $\forall X \subset V$，$X$ 导出子图的边数 $\div$ $|X|$ $< D$。

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

Yes
No

提示

制約

• $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) $

Sample Explanation 1

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