AT_abc239_f [ABC239F] Construct Highway

在 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_2$ $\ldots$ $D_N$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_M$ $B_M$

如果不存在满足条件的建设方案，输出 `-1`。 如果存在，请输出 $N-M-1$ 行，每行输出一条新建高速公路所连接的两个城市的编号，编号之间用空格隔开。

## 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $0 \leq M < N-1$ - $1 \leq D_i \leq N-1$ - $1 \leq A_i < B_i \leq N$ - 若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$ - 输入中的所有数值均为整数 ## 样例说明 1 如输出样例所示，如果新建连接城市 $6$ 和 $2$、城市 $5$ 和 $6$、城市 $4$ 和 $5$ 的高速公路，则可以满足条件。除此之外，例如新建连接城市 $6$ 和 $4$、城市 $5$ 和 $6$、城市 $2$ 和 $5$ 的高速公路，也可以满足条件。 由 ChatGPT 4.1 翻译