题目描述

我们将非空顶点集合的简单无向图的密度定义为 $\displaystyle\frac{(\text{边数})}{(\text{顶点数})}$。

给定正整数 $N,\ D$，以及一个有 $N$ 个顶点、$DN$ 条边的简单无向图 $G$。$G$ 的顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。请判断 $G$ 是否满足以下条件。

条件： 设 $G$ 的顶点集合为 $V$。对于 $V$ 的任意非空真子集 $X$，由 $X$ 所诱导的 $G$ 的子图的密度严格小于 $D$。

诱导子图的定义如下：

对于图 $G$ 的顶点子集 $X$，由 $X$ 所诱导的 $G$ 的子图，是指“顶点集合为 $X$，边集合为『$G$ 中连接 $X$ 内任意两点的所有边』的图”。注意，上述条件只考虑既不是空集也不是全集的顶点子集。

输入格式

输入按以下格式从标准输入读入。

$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$ 个测试用例，如果给定的图 $G$ 满足条件，则输出 Yes，否则输出 No。

样例 1

输入

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$
• 所有测试用例中 $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)$

样例解释 1

• 第 1 个测试用例与问题 D的输出样例 1 相同，满足条件。
• 对于第 2 个测试用例，顶点集合 $\{1, 2, 3, 4\}$ 的非空真子集 $\{1, 2, 3\}$ 所诱导的子图的边集合为 $\{(1, 2), (1, 3), (2, 3)\}$，其密度为 $\displaystyle\frac{3}{3}=1=D$。因此，该图不满足条件。

由 ChatGPT 4.1 翻译