Construct Highway

题目描述

The Republic of Atcoder 有 $N$ 个城镇，编号为 $1$ 到 $N$，以及 $M$ 条高速公路，编号为 $1$ 到 $M$。
高速公路 $i$ 双向连接城镇 $A_i$ 和城镇 $B_i$。 国王高桥将要建设 $(N-M-1)$ 条新高速公路，使得满足以下两个条件：

可以通过若干条高速公路在任意一对城镇之间往返 对于每个 $i=1,\ldots,N$，恰好有 $D_i$ 条高速公路直接连接到城镇 $i$

判断是否存在这样的建设方法。如果存在，输出其中一种方案。

输入格式

输入按下列格式由标准输入提供： $N$ $M$ $D_1$ $\ldots$ $D_N$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

如果不存在满足条件的建设方法，输出 $-1$.
如果存在，输出 $(N-M-1)$ 行。第 $i$ 行应包含第 $i$ 条要建设的高速公路所连接的两个城镇的编号。

6 2
1 2 1 2 2 2
2 3
1 4

6 2
5 6
4 5

5 1
1 1 1 1 4
2 3

-1

4 0
3 3 3 3

-1

提示

$2 \leq N \leq 2\times 10^5$ $0 \leq M \lt N-1$ $1 \leq D_i \leq N-1$ $1\leq A_i \lt B_i \leq N$ 如果 $i\neq j$，则 $(A_i, B_i) \neq (A_j,B_j)$。 输入中的所有数值均为整数。如样例输出所示，通过依次建设连接城镇 $6$ 和 $2$、城镇 $5$ 和 $6$、城镇 $4$ 和 $5$ 的高速公路可以满足条件。 另一种满足条件的例子是依次建设连接城镇 $6$ 和 $4$、城镇 $5$ 和 $6$、城镇 $2$ 和 $5$ 的高速公路。

标签: AtCoder|abc239F

来源

AtCoder|abc239F