题目描述

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

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

高达(High King)高桥王准备修建$(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