当前没有测试数据。

F - 建设高速公路

得分: $500$ 分

问题描述

Atcoder 共和国有 $N$ 个编号为 $1$ 到 $N$ 的城镇，以及 $M$ 条编号为 $1$ 到 $M$ 的高速公路。
高速公路 $i$ 双向连接城镇 $A_i$ 和城镇 $B_i$。

王子高文打算建设 $(N-M-1)$ 条新的高速公路以满足以下两个条件:

• 可以使用一些高速公路在每一对城镇之间旅行
• 对于每个 $i=1,\ldots,N$，恰好有 $D_i$ 条高速公路直接连接到城镇 $i$

判断是否有这样的建设方式。如果存在，请输出一种方案。

约束

• $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)$。
• 输入中的所有值都是整数。

输入

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

$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

如样例输出所示，可以通过连接城镇 $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