AT_arc161_d.[ARC161D] Everywhere is Sparser than Whole (Construction)

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

给定正整数 $ N,\ D $，请判断是否存在一个具有 $ N $ 个顶点、$ DN $ 条边的简单无向图 $ G $，满足以下条件。若存在，请构造出任意一个满足条件的图。

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

关于诱导子图的定义如下：

对图 $ G $ 的顶点子集 $ X $，由 $ X $ 构成的诱导子图是指“顶点集合为 $ X $，边集合为『属于 $ G $ 且连接 $ X $ 中两个顶点的所有边』的图”。注意，此条件中只考虑非空且不等于全集的顶点子集。

输入从标准输入中给出，格式如下：

$ N $ $ D $

若存在满足条件的简单无向图，则输出 Yes，否则输出 No。若输出 Yes，接下来输出 $ DN $ 行，描述所构造的图，格式如下：

$ A_1 $ $ B_1 $
$ A_2 $ $ B_2 $
$ \vdots $
$ A_{DN} $ $ B_{DN} $

• $ 1\ \leq\ A_i,\ B_i\ \leq\ N\ (1\ \leq\ i\ \leq\ DN) $
• $ A_i\ \neq\ B_i\ (1\ \leq\ i\ \leq\ DN) $
• $ {A_i,\ B_i}\ \neq\ {A_j,\ B_j}\ (1\ \leq\ i\ <\ j\ \leq\ DN) $
• 图的顶点编号为 $ 1 $ 到 $ N $。
• 第 $ i $ 行输出表示第 $ i $ 条边连接顶点 $ A_i $ 与 $ B_i $。
• 边的顺序（哪条边先输出）和每条边端点的顺序（先输出哪个顶点）没有限制。

限制条件

• $ N\ \geq\ 1 $；
• $ D\ \geq\ 1 $；
• $ DN\ \leq\ 5\ \times\ 10^4 $。

样例解释 1

输出的图的顶点集合为 $ {1,\ 2,\ 3} $，边集合为 $ {(1,\ 2),\ (1,\ 3),\ (2,\ 3)} $，满足简单图的定义。对非空真子集 $ X $ 有 $ 6 $ 种情况：

• 当 $ X = {1},\ {2},\ {3} $ 时，诱导子图的边集合为空，密度为 $ \displaystyle\frac{0}{1} = 0 $；
• 当 $ X = {1,\ 2},\ {1,\ 3},\ {2,\ 3} $ 时，诱导子图的边集合分别为 $ {(1,\ 2)},\ {(1,\ 3)},\ {(2,\ 3)} $，密度均为 $ \displaystyle\frac{1}{2} $。

所以所有诱导子图的密度都严格小于 $ D = 1 $，该图满足条件。

样例解释 2

不存在一个简单无向图同时满足 $ 4 $ 个顶点和 $ 8 $ 条边的要求。

翻译由 GPT-4o 提供。