图建设性问题又回来了!这次要求您构建的图表应与以下属性匹配。
当且仅当每对顶点之间存在路径时,图才是连通的。
连接无向图的直径(又名“最长最短路径”)是其任意一对顶点之间的最短路径中的最大边数。
顶点的度数是与其相关的边的数量。
给定 $$$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$$$