题目描述

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

给定正整数 $N$、$D$，以及一个有 $N$ 个顶点和 $DN$ 条边的简单无向图 $G$。图 $G$ 的顶点从 $1$ 到 $N$ 进行标号，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。确定图 $G$ 是否满足以下条件。

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

需要解决 $T$ 个测试用例。

什么是引出的子图？

对于图 $G$ 的顶点子集 $X$，由顶点集合 $X$ 引出的子图是指在顶点集合为 $X$ 并且边集包含所有连接顶点集合 $X$ 中的两个顶点的边的图。在上述条件中，注意我们只考虑既不为空集也不是整个集合的顶点子集。

约束条件

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

输入

从标准输入读取输入，其格式如下：

$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

• 第一个测试用例与问题 D中的示例输入 1 相同，并且满足条件。
• 对于第二个测试用例，由顶点集合 $\\{1, 2, 3\\}$ 引出的子图的边集为 $\\{(1, 2), (1, 3), (2, 3)\\}$，其密度为 $\\displaystyle\\frac{3}{3} = 1 = D$。因此，该图不满足条件。