CF1082D.Maximum Diameter Graph

普及+/提高

通过率：0%

时间限制：2.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Graph constructive problems are back! This time the graph you are asked to build should match the following properties.

The graph is connected if and only if there exists a path between every pair of vertices.

The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.

The degree of a vertex is the number of edges incident to it.

Given a sequence of $n$ integers $a_1, a_2, \dots, a_n$ construct a connected undirected graph of $n$ vertices such that:

the graph contains no self-loops and no multiple edges;
the degree $d_i$ of the $i$ -th vertex doesn't exceed $a_i$ (i.e. $d_i \le a_i$ );
the diameter of the graph is maximum possible.

Output the resulting graph or report that no solution exists.

图构造类问题又来了！这次你需要构造的图需满足以下性质：

当且仅当任意两个顶点之间均存在路径时，该图是连通的。

连通无向图的直径（又称“最长最短路径”）是指其任意两个顶点间最短路径所含边数的最大值。

一个顶点的度是指与其关联的边的数量。

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ ，请构造一个包含 $n$ 个顶点的连通无向图，使得：

该图不含自环和重边；
第 $i$ 个顶点的度 $d_i$ 不超过 $a_i$ （即 $d_i \le a_i$ ）；
该图的直径尽可能大。

输出所构造的图，或判定无解。

输入格式

The first line contains a single integer $n$ ( $3 \le n \le 500$ ) — the number of vertices in the graph.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le n - 1$ ) — the upper limits to vertex degrees.

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

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

输出格式

Print "NO" if no graph can be constructed under the given conditions.

Otherwise print "YES" and the diameter of the resulting graph in the first line.

The second line should contain a single integer $m$ — the number of edges in the resulting graph.

The $i$ -th of the next $m$ lines should contain two integers $v_i, u_i$ ( $1 \le v_i, u_i \le n$ , $v_i \neq u_i$ ) — the description of the $i$ -th edge. The graph should contain no multiple edges — for each pair $(x, y)$ you output, you should output no more pairs $(x, y)$ or $(y, x)$ .

如果无法在给定条件下构造出图，则输出 "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
```

说明/提示

Here are the graphs for the first two example cases. Both have diameter of $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$

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