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

由 ChatGPT 4.1 翻译