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\

### 限制条件 - $ 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 提供。