分数: 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