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$ 行，每行输出一条新建高速公路所连接的两个城市的编号，编号之间用空格隔开。

输入输出样例 #1

输入 #1

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

输出 #1

6 2
5 6
4 5

输入输出样例 #2

输入 #2

5 1
1 1 1 1 4
2 3

输出 #2

-1

输入输出样例 #3

输入 #3

4 0
3 3 3 3

输出 #3

-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 翻译