C - Chain Blackout Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はある地域の電力網を管理しています。この電力網には N 個の変電所があり、変電所には 1 から 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 に電力が流入する送電線の本数、すなわち V_k = i を満たす送電線 k の本数（有向グラフとしての変電所 i の入次数）に等しいです。

この電力網では、変電所の負荷が耐久値を超えると停電が発生し、それが連鎖的に広がる可能性があります。具体的な手順は以下の通りです。

なお、一度停電を起こした変電所の負荷はその後変化しません。

  1. 停電の発生： まだ停電を起こしていない変電所の中に、負荷が耐久値を真に超えているもの（すなわち、変電所 j について 負荷 > T_j であるもの）が存在すれば、その中からどれか一つを選ぶ。選んだ変電所を変電所 s とする。そのような変電所が存在しなければ、連鎖は終了する。
  2. 停電の処理： 変電所 s は停電を起こし、機能を停止する。変電所 s からの送電が途絶えるため、送電先の各変電所は不足した電力を他の経路から補おうとし、その結果負荷が増大する。具体的には、U_k = s であるような各送電線 k について、送電先の変電所 V_k がまだ停電を起こしていなければ、変電所 V_k の負荷を 1 増加させる（既に停電を起こしている変電所の負荷は変化しない）。
  3. 繰り返し： 手順 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
  • 1 行目には、変電所の数 N と送電線の数 M が、スペース区切りで与えられる。
  • 2 行目には、各変電所の耐久値 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
  • 続く M 行のうち k 行目（1 \leq k \leq M）には、送電線 k の情報として U_k と V_k がスペース区切りで与えられる。これは変電所 U_k から変電所 V_k へ電力を供給する送電線があることを意味する。

出力

最終的に停電を起こした変電所の番号を昇順にスペース区切りで 1 行で出力せよ。停電を起こした変電所が 1 つもない場合は、代わりに -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

Score : 366 pts

Problem Statement

Takahashi manages the power grid of a certain region. This power grid has N substations, numbered from 1 to N.

There are M transmission lines laid between substations. Transmission line k (1 \leq k \leq M) supplies power in the direction from substation U_k to substation V_k. There are no self-loops (U_k \neq V_k). Also, the same ordered pair (U_k, V_k) does not appear more than once. However, for two substations u, v, it is possible for a transmission line from substation u to substation v and a transmission line from substation v to substation u to exist simultaneously.

Each substation i (1 \leq i \leq N) has a durability value T_i. Also, each substation i has a non-negative integer value called its load. Initially, all substations are operational, and the load of substation i equals the number of transmission lines through which power flows into substation i, that is, the number of transmission lines k satisfying V_k = i (the in-degree of substation i in the directed graph).

In this power grid, when a substation's load exceeds its durability value, a blackout occurs, and it may spread in a chain reaction. The specific procedure is as follows.

Note that the load of a substation that has already experienced a blackout does not change afterwards.

  1. Blackout occurrence: Among the substations that have not yet experienced a blackout, if there exists one whose load strictly exceeds its durability value (that is, for substation j, load > T_j), choose any one of them. Let the chosen substation be substation s. If no such substation exists, the chain ends.
  2. Blackout processing: Substation s experiences a blackout and ceases to function. Since power transmission from substation s is cut off, each destination substation tries to compensate for the lost power through other routes, resulting in increased load. Specifically, for each transmission line k such that U_k = s, if the destination substation V_k has not yet experienced a blackout, the load of substation V_k is increased by 1 (the load of substations that have already experienced a blackout does not change).
  3. Repeat: Return to step 1.

Since the number of substations is finite, this chain always terminates in a finite number of steps.

Note: It can be proven that regardless of which substation is chosen when multiple substations satisfy the condition in step 1, the final set of substations that experience a blackout is the same. Therefore, the answer is uniquely determined.

When the chain has completely settled (that is, when no substation that has not yet experienced a blackout has a load strictly exceeding its durability value), find all the substation numbers that ultimately experienced a blackout.

Constraints

  • 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)
  • The same ordered pair (U_k, V_k) does not appear more than once
  • All input values are integers

Input

N M
T_1 T_2 \ldots T_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains the number of substations N and the number of transmission lines M, separated by a space.
  • The second line contains the durability values T_1, T_2, \ldots, T_N of each substation, separated by spaces.
  • In the following M lines, the k-th line (1 \leq k \leq M) contains U_k and V_k separated by a space, representing the information of transmission line k. This means there is a transmission line supplying power from substation U_k to substation V_k.

Output

Output the numbers of all substations that ultimately experienced a blackout, in ascending order, separated by spaces, on a single line. If no substation experienced a blackout, output -1 instead.

Sample Input 1

5 5
0 1 1 1 1
1 2
1 3
2 3
3 4
4 5

Sample Output 1

3 4 5

Sample Input 2

3 2
0 1 1
1 2
1 3

Sample Output 2

-1

Sample Input 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

Sample Output 3

4 5 6 7

Sample Input 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

Sample Output 4

3 4 5 6 7 8 9 10

Sample Input 5

1 0
0

Sample Output 5

-1