修建高速公路

题目描述

AtCoder 共和国有 $N$ 个城镇,编号为 $1$ 到 $N$,以及 $M$ 条高速公路,编号为 $1$ 到 $M$。

高速公路 $i$ 双向连接城镇 $A_i$ 和城镇 $B_i$。

高桥国王将新建 $(N-M-1)$ 条高速公路,使得以下两个条件得到满足:

• 任意两个城镇之间都可以通过若干条高速公路互相到达。
• 对于每个 $i=1,\ldots,N$,与城镇 $i$ 直接相连的高速公路恰好有 $D_i$ 条。

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

输入格式

输入按以下格式从标准输入给出:

N M
D_1 … D_N
A_1 B_1
⋮
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

如样例输出所示,可以分别通过修建连接城镇 $6$ 和 $2$、城镇 $5$ 和 $6$、城镇 $4$ 和 $5$ 的高速公路来满足条件。

另一种满足条件的方案是分别修建连接城镇 $6$ 和 $4$、城镇 $5$ 和 $6$、城镇 $2$ 和 $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)$。
• 输入中的所有值均为整数。