分数: 366 分
问题陈述
高桥管理某个地区的电网。这个电网有 N 变电站,编号自 1 to N.
有 M 变电站之间铺设的输电线路。传输线 k (1 \leq k \leq M) 从变电站方向供电 U_k 至变电站 V_k。不存在自循环(U_k \neq V_k)。另外,相同的有序对 (U_k, V_k) 不会出现多次。然而,对于两个变电站 u, v,有可能来自变电站的传输线 u 至变电站 v 和来自变电站的传输线 v 至变电站 u 同时存在。
各变电站 i (1 \leq i \leq N)有一个 耐久值 T_i。另外,各变电站 i 有一个非负整数值,称为其 负载。初始阶段,所有变电站均投入运行,变电站负荷 i 等于电力流入变电站的输电线路的数量 i,即传输线数 k 满意 V_k = i (变电站入度 有向图中的 i )。
在该电网中,当变电站的负荷超过其耐久值时,就会发生停电,并且可能会连锁反应蔓延。具体流程如下。
请注意 已经经历过停电的变电站的负载在之后不会发生变化。
- 停电发生: 尚未停电的变电站中,是否存在负荷 严格超过 其耐久值(即对于变电站 j,负载 > T_j),选择其中任意一项。设所选变电站为变电站 s。如果不存在这样的变电站,则链结束。
- 停电处理: 变电站 s 遇到停电并停止运行。由于变电站送电 s 被切断,每个目的地变电站试图通过其他路线补偿损失的电力,导致负载增加。具体来说,对于每条传输线 k 这样 U_k = s,如果目的地变电站 V_k 尚未经历停电,变电站负荷 V_k 增加 1 (已经停电的变电站负荷不变)。
- 重复: 返回步骤 1。
由于变电站的数量是有限的,因此该链始终以有限数量的步骤终止。
注意: 可以证明,当多个变电站满足步骤1的条件时,无论选择哪个变电站,最终发生停电的变电站集合都是相同的。因此,答案是唯一确定的。
当链完全稳定后(即,当尚未发生停电的变电站均没有严格超过其耐久值的负载时),查找最终发生停电的所有变电站号。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 0 \leq T_i \leq N (1 \leq i \leq N)
- 1 \leq U_k \leq N (1 \leq k \leq M)
- 1 \leq V_k \leq N (1 \leq k \leq M)
- U_k \neq V_k (1 \leq k \leq M)
- 相同的有序对 (U_k, V_k) 出现次数不超过一次
- 所有输入值均为整数
输入
N M T_1 T_2 \ldots T_N U_1 V_1 U_2 V_2 \vdots U_M V_M
- 第一行包含变电站的数量 N 和传输线的数量 M,用空格分隔。
- 第二行包含耐久性值 每个变电站的 T_1, T_2, \ldots, T_N ,以空格分隔。
- 如下 M 行, k- 第行 (1 \leq k \leq M) 包含 U_k 和 V_k 以空格分隔,代表传输线路信息 k。这意味着有一条输电线路从变电站供电 U_k 至变电站 V_k.
输出
在一行中按升序输出最终停电的所有变电站的编号,并以空格分隔。如果没有变电站发生停电,则输出 -1 代替。
示例输入 1
5 5 0 1 1 1 1 1 2 1 3 2 3 3 4 4 5
示例输出 1
3 4 5
示例输入 2
3 2 0 1 1 1 2 1 3
示例输出 2
-1
示例输入 3
7 9 0 1 1 1 1 2 2 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 2 6
示例输出 3
4 5 6 7
示例输入 4
10 12 0 1 1 1 1 1 1 1 2 1 1 2 1 3 2 3 3 4 3 5 4 6 5 6 6 7 6 8 7 9 8 9 9 10
示例输出 4
3 4 5 6 7 8 9 10
示例输入 5
1 0 0
示例输出 5
-1