← 返回题目列表

Codeforces · 1082/D

D. 最大直径图

中文机器翻译题面 查看原题

图建设性问题又回来了!这次要求您构建的图表应与以下属性匹配。

当且仅当每对顶点之间存在路径时,图才是连通的。

连接无向图的直径(又名“最长最短路径”)是其任意一对顶点之间的最短路径中的最大边数。

顶点的度数是与其相关的边的数量。

给定 $$$n$$$ 整数序列 $$$a_1, a_2, \dots, a_n$$$ 构造 $$$n$$$ 顶点的连通无向图,使得:

- 该图不包含自环且不包含重边;
- 第 $$$i$$$ 个顶点的度 $$$d_i$$$ 不超过 $$$a_i$$$ (即 $$$d_i \le a_i$$$);
- 图形的直径是最大可能的。

输出结果图或报告不存在解。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 500$$$) — 图中的顶点数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n - 1$$$) — 顶点度数的上限。

输出

如果在给定条件下无法构建图表,则打印“NO”。

否则在第一行打印“YES”和结果图的直径。

第二行应包含一个整数 $$$m$$$ — 结果图中的边数。

接下来的 $$$m$$$ 行的第 $$$i$$$ 行应包含两个整数 $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \neq u_i$$$) — 第 $$$i$$$ 条边的描述。该图不应包含多个边 - 对于您输出的每对 $$$(x, y)$$$,您不应再输出更多对 $$$(x, y)$$$ 或 $$$(y, x)$$$。

示例

输入 #1

3
2 2 2

输出 #1

YES 2
2
1 2
2 3

输入 #2

5
1 4 1 1 1

输出 #2

YES 2
4
1 2
3 2
4 2
5 2

输入 #3

3
1 1 1

输出 #3

NO

注意

以下是前两个示例情况的图表。两者的直径均为$$$2$$$。

$$$d_1 = 1 \le a_1 = 2$$$$$$d_2 = 2 \le a_2 = 2$$$$$$d_3 = 1 \le a_3 = 2$$$

$$$d_1 = 1 \le a_1 = 1$$$$$$d_2 = 4 \le a_2 = 4$$$$$$d_3 = 1 \le a_3 = 1$$$$$$d_4 = 1 \le a_4 = 1$$$