H - City Tour Survey Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はある地域の調査員です。この地域には N 個の都市があり、都市には 1 から N までの番号が付けられています。都市同士は一方通行の道路で結ばれており、道路は全部で M 本あります。道路 j は都市 U_j から都市 V_j への一方通行で、この道路を使うと都市 U_j から都市 V_j へ直接移動できます（逆方向には移動できません）。

各都市にはそれぞれ異なる重要度が設定されています。都市 i の重要度は B_i です。B_1, B_2, \ldots, B_N は 1 から N までの整数を並べ替えたもの（順列）です。

高橋君は以下の手順を繰り返し、すべての都市を調査します。はじめ、すべての都市は未調査です。

  1. 出発都市を決める。 1回目の巡回では都市 1 を出発都市とする。2回目以降の巡回では、未調査の都市のうち重要度が最も大きい都市を出発都市とする。
  2. 出発都市から巡回を行う。 まず出発都市を調査済みにする。その後、以下の操作を繰り返す：
  • 現在いる都市から1本の道路で直接移動できる都市の中に、未調査の都市が1つ以上存在するならば、その中で重要度が最も大きい都市へ移動し、その都市を調査済みにする。
  • 現在いる都市から1本の道路で直接移動できる都市の中に未調査の都市が存在しない場合（移動できる都市自体が存在しない場合を含む）、この巡回を終了する。
  1. すべての都市が調査済みになっていれば終了する。そうでなければ手順 1 に戻る。

高橋君が都市を調査済みにした順序を、先頭から順にすべて出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq B_i \leq N
  • B_1, B_2, \ldots, B_N はすべて異なる
  • 1 \leq U_j \leq N
  • 1 \leq V_j \leq N
  • U_j \neq V_j
  • 同じ (U_j, V_j) の組は複数回与えられない
  • 入力はすべて整数である

入力

N M
B_1 B_2 \ldots B_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、都市の数を表す N と道路の本数を表す M が、スペース区切りで与えられる。
  • 2 行目には、都市 i の重要度を表す B_i が N 個、スペース区切りで与えられる。B_1, B_2, \ldots, B_N はすべて異なる。
  • 3 行目から M 行にわたり、道路の情報が与えられる。2 + j 行目では、都市 U_j から都市 V_j への一方通行の道路があることを表す。

出力

高橋君が都市を調査済みにした順序を、スペース区切りで 1 行に出力せよ。出力される都市番号はちょうど N 個であり、1 から N の各番号がちょうど 1 回ずつ現れる。

入力例 1

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

出力例 1

1 2 4 3 5

入力例 2

4 0
2 4 3 1

出力例 2

1 2 3 4

入力例 3

8 8
4 7 2 8 1 6 3 5
1 2
1 4
2 3
2 5
4 6
6 7
7 8
3 8

出力例 3

1 4 6 7 8 2 3 5

入力例 4

10 9
5 10 3 8 1 9 2 7 4 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

出力例 4

1 2 3 4 5 6 7 8 9 10

入力例 5

1 0
1

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is a surveyor for a certain region. This region contains N cities, numbered from 1 to N. The cities are connected by one-way roads, and there are M roads in total. Road j is a one-way road from city U_j to city V_j, allowing direct travel from city U_j to city V_j (travel in the reverse direction is not possible).

Each city has a distinct importance value assigned to it. The importance of city i is B_i. B_1, B_2, \ldots, B_N is a permutation of the integers from 1 to N.

Takahashi surveys all cities by repeating the following procedure. Initially, all cities are unsurveyed.

  1. Determine the starting city. For the first tour, the starting city is city 1. For each subsequent tour, the starting city is the unsurveyed city with the highest importance.
  2. Conduct a tour from the starting city. First, mark the starting city as surveyed. Then, repeat the following operation:
  • If there exists at least one unsurveyed city among the cities directly reachable by a single road from the current city, move to the one with the highest importance among them, and mark that city as surveyed.
  • If there are no unsurveyed cities among the cities directly reachable by a single road from the current city (including the case where no reachable cities exist at all), end this tour.
  1. If all cities have been surveyed, stop. Otherwise, return to step 1.

Output, in order from first to last, the sequence in which Takahashi marks cities as surveyed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq B_i \leq N
  • B_1, B_2, \ldots, B_N are all distinct
  • 1 \leq U_j \leq N
  • 1 \leq V_j \leq N
  • U_j \neq V_j
  • The same pair (U_j, V_j) is not given more than once
  • All input values are integers

Input

N M
B_1 B_2 \ldots B_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains N, the number of cities, and M, the number of roads, separated by a space.
  • The second line contains N space-separated values B_i, representing the importance of city i. B_1, B_2, \ldots, B_N are all distinct.
  • The following M lines provide road information. The (2 + j)-th line indicates that there is a one-way road from city U_j to city V_j.

Output

Output the order in which Takahashi marks cities as surveyed, on a single line separated by spaces. The output should contain exactly N city numbers, with each number from 1 to N appearing exactly once.

Sample Input 1

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

Sample Output 1

1 2 4 3 5

Sample Input 2

4 0
2 4 3 1

Sample Output 2

1 2 3 4

Sample Input 3

8 8
4 7 2 8 1 6 3 5
1 2
1 4
2 3
2 5
4 6
6 7
7 8
3 8

Sample Output 3

1 4 6 7 8 2 3 5

Sample Input 4

10 9
5 10 3 8 1 9 2 7 4 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Sample Output 4

1 2 3 4 5 6 7 8 9 10

Sample Input 5

1 0
1

Sample Output 5

1