F - Construct Highway 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

Atcoder 国には 1 から N の番号がついた N 個の街と 1 から M の番号がついた M 個の高速道路があります。
高速道路 i は街 A_i と街 B_i を双方向に結んでいます。

国王の高橋君は、新たに N-M-1 本の高速道路を建設し、次の 2 つの条件をともに満たそうとしています。

  • すべての街同士は、高速道路をいくつか通って互いに行き来できる
  • 各 i=1,\ldots,N について、街 i はちょうど D_i 本の高速道路と直接つながっている

条件を満たすような建設方法が存在するか判定し、存在するなら 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)
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

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

出力

条件を満たすような建設方法が存在しないとき -1 を出力せよ。
存在するとき、N-M-1 行出力せよ。i 行目には、i 番目に建設する高速道路が結ぶ 2 つの街の番号を空白区切りで出力せよ。

入力例 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

Score : 500 points

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