← 返回题目列表

AtCoder · abc239_f

I. 建设高速公路

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

Atcoder共和国有 N 城镇编号 1 通过 N,和 M 高速公路编号 1 通过 M.
高速公路 i 连接城镇 A_i 和镇 B_i 双向。

高桥王要建造 (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
  • If 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