AT_arc161_f [ARC161F] Everywhere is Sparser than Whole (Judge)

我们将非空顶点集合的简单无向图的**密度**定义为 $ \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`。

### 限制条件 - $ 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](./arc161_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 翻译