102395: [AtCoder]ABC239 F - Construct Highway

Problem Statement

The Republic of Atcoder has $N$ towns numbered $1$ through $N$, and $M$ highways numbered $1$ through $M$.
Highway $i$ connects Town $A_i$ and Town $B_i$ bidirectionally.

King Takahashi is going to construct $(N-M-1)$ new highways so that the following two conditions are satisfied:

• One can travel between every pair of towns using some number of highways
• For each $i=1,\ldots,N$, exactly $D_i$ highways are directly connected to Town $i$

Determine if there is such a way of construction. If it exists, print one.

Constraints

• $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$
• If $i\neq j$, then $(A_i, B_i) \neq (A_j,B_j)$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$D_1$ $\ldots$ $D_N$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

Output

If there isn't a way of construction that satisfies the conditions, print -1.
If there is, print $(N-M-1)$ lines. The $i$-th line should contain the indices of the two towns connected by the $i$-th highway to be constructed.

Sample Input 1

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

Sample Output 1

6 2
5 6
4 5

As in the Sample Output, the conditions can be satisfied by constructing highways connecting Towns $6$ and $2$, Towns $5$ and $6$, and Towns $4$ and $5$, respectively.

Another example to satisfy the conditions is to construct highways connecting Towns $6$ and $4$, Towns $5$ and $6$, and Towns $2$ and $5$, respectively.

Sample Input 2

5 1
1 1 1 1 4
2 3

Sample Output 2

-1

Sample Input 3

4 0
3 3 3 3

Sample Output 3

-1

问题描述

Atcoder共和国共有$N$个城镇，编号为1到$N$，共有$M$条高速公路，编号为1到$M$。

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

国王Takahashi打算新建$(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$条高速公路连接的两个城镇的索引。

样例输入1

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

样例输出1

6 2
5 6
4 5

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

另一种满足条件的例子是分别建造连接城镇6和4、城镇5和6以及城镇2和5的高速公路。

样例输入2

5 1
1 1 1 1 4
2 3

样例输出2

-1

样例输入3

4 0
3 3 3 3

样例输出3

-1