分数: 500 点
问题陈述
我们定义 密度 非空简单无向图的 为 \displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}.
给你正整数 N 和 D。判断是否存在简单无向图 G 与 N 顶点和 DN 满足以下条件的边。如果存在,请找到一张这样的图。
条件: 让 V 是顶点集 G。 对于任意非空 正确 子集 X of V,导出子图的密度 G by X is 严格小于 D.
什么是诱导子图?
对于顶点子集 图的 X 图表的 G, 诱导子图 of G by X 是带有顶点集的图 X 和包含所有边的边集 G 连接两个顶点 X。 在上述条件下,请注意,我们只考虑既不为空也不为整个集合的顶点子集。
约束
- N \geq 1
- D \geq 1
- DN \leq 5 \times 10^4
输入
输入由标准输入按以下格式给出:
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 to N.
- 的 i输出的第行表示 i第一条边连接顶点 A_i 和顶点 B_i.
- 边的顺序(首先打印哪个边)和顶点的顺序(首先打印每个边的哪个端点)可以是任意的。
示例输入 1
3 1
示例输出 1
Yes 1 2 1 3 2 3
打印的图形已设置顶点 \{1, 2, 3\} 和边缘设置 \{(1, 2), (1, 3), (2, 3)\},而且很简单。 顶点集 X 有 6 非空真子集: \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}.
- 对于 X = \{1\}, \{2\}, \{3\},归纳子图的边集 X 为空,密度为 \displaystyle\frac{0}{1} = 0.
- 对于 X = \{1, 2\}, \{1, 3\}, \{2, 3\},归纳子图的边集 X 是 \{(1, 2)\}, \{(1, 3)\}, \{(2, 3)\}分别为,密度均为 \displaystyle\frac{1}{2}.
在所有情况下,导出子图的密度严格小于 D = 1,所以该图满足条件。
示例输入 2
4 2
示例输出 2
No
一个简单的无向图 4 顶点和 8 边不存在。