I - Evacuation Plan Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

ある都市には村が N 個あり、村 1 から村 N まで番号付けされています。村 i は標高 H_i にあります。 どの 2 つの村も同じ標高にはありません。
2 つの村を繋ぐ水路が M 本あり、i 番目の水路は村 A_i と村 B_i を結びます。水路は標高が高い側の村から低い側の村へのみ通行可能です。
この都市では、村 C_1, C_2, C_3, \dots, C_K の K 個の村が災害発生時の避難所として指定されています。
N 個全ての村について、その村から 0 本以上の水路を使っていずれかの避難所に辿りつくことができるか、できるなら最小で何本の水路を通ればよいかを求めてください。

制約

  • 2 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le K \le N
  • 1 \le H_i \le 10^9
  • H_i \neq H_j (i \neq j)
  • 1 \le C_i \le N
  • C_i \neq C_j (i \neq j)
  • 1 \le A_i \le N
  • 1 \le B_i \le N
  • A_i \neq B_i
  • (A_i, B_i) \neq (A_j, B_j) (i \neq j)
  • (A_i, B_i) \neq (B_j, A_j) (i \neq j)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
H_1 H_2 H_3 \dots H_N
C_1 C_2 C_3 \dots C_K
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M

出力

N 行に渡って出力せよ。 i 行目には、村 i からいずれかの避難所に辿りつくことができるなら辿りつくのに必要な最小の本数を、辿りつくことができないなら -1 を出力せよ。

入力例 1

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

出力例 1

0
0
1
1
2
  • 村 1 : 村 1 自身が避難所に指定されているので、使用する水路の最小の本数は 0 です。
  • 村 2 : 村 2 自身が避難所に指定されているので、使用する水路の最小の本数は 0 です。
  • 村 3 : 村 3 の方が村 1 より標高が高いので、2 番目の水路を使って避難所に指定されている村 1 に移動することができます。使う水路の本数は 1 で、これが最小です。
  • 村 4 : 村 4 の方が村 2 より標高が高いので、3 番目の水路を使って避難所に指定されている村 2 に移動することができます。使う水路の本数は 1 で、これが最小です。
  • 村 5 : 5 番目の水路を使って村 3 に移動し、更に 2 番目の水路を使って避難所に指定されている村 1 に移動することができます。使う水路の本数は 2 で、これが最小です。

入力例 2

5 6 2
6 5 9 15 3
4 2
1 5
2 5
2 4
1 3
4 3
2 1

出力例 2

1
0
2
0
-1

村 5 からはどこにも行くことができず、村 5 自身が避難所に指定されていることもないので、5 行目には -1 を出力します。

入力例 3

5 4 2
3 10 5 8 2
3 5
3 2
3 1
4 5
2 1

出力例 3

-1
1
0
1
0

Score : 6 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In a city, there are N villages, numbered 1 through N. The elevation of Village i is H_i. No two villages are at the same elevation.
There are M waterways, each of which connects two villages; the i-th waterway connects Village A_i and Village B_i. You can only go through a waterway from the village with the higher elevation to the village with the lower elevation.
In this city, K of the villages - Villages C_1, C_2, C_3, \dots, C_K - are specified as places of refuge in times of disaster.
For each village, determine whether it is possible to reach one of the places of refuge using zero or more waterways. If it is possible, also find the minimum number of waterways that must be traversed to reach a place of refuge from that village.

Constraints

  • 2 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le K \le N
  • 1 \le H_i \le 10^9
  • H_i \neq H_j (i \neq j)
  • 1 \le C_i \le N
  • C_i \neq C_j (i \neq j)
  • 1 \le A_i \le N
  • 1 \le B_i \le N
  • A_i \neq B_i
  • (A_i, B_i) \neq (A_j, B_j) (i \neq j)
  • (A_i, B_i) \neq (B_j, A_j) (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K
H_1 H_2 H_3 \dots H_N
C_1 C_2 C_3 \dots C_K
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M

Output

Print N lines. If a place of refuge is reachable from Village i, the i-th line should contain the minimum number of waterways that must be traversed to reach a place of refuge; otherwise, the line should contain -1.

Sample Input 1

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

Sample Output 1

0
0
1
1
2
  • Village 1: since it is a place of refuge itself, the minimum number of waterways that must be traversed is 0.
  • Village 2: since it is a place of refuge itself, the minimum number of waterways that must be traversed is 0.
  • Village 3: since its elevation is higher than that of Village 1, we can traverse the 2-nd waterway to go to Village 1, which is a place of refuge. We have traversed 1 waterway, which is the minimum number needed.
  • Village 4: since its elevation is higher than that of Village 2, we can traverse the 3-rd waterway to go to Village 2, which is a place of refuge. We have traversed 1 waterway, which is the minimum number needed.
  • Village 5: we can traverse the 5-th waterway to go to Village 3, and then traverse the 2-nd waterway to go to Village 1, which is a place of refuge. We have traversed 2 waterway, which is the minimum number needed.

Sample Input 2

5 6 2
6 5 9 15 3
4 2
1 5
2 5
2 4
1 3
4 3
2 1

Sample Output 2

1
0
2
0
-1

From Village 5, we cannot go to any other village. It is not a place of refuge itself, either, so the 5-th line should contain -1.

Sample Input 3

5 4 2
3 10 5 8 2
3 5
3 2
3 1
4 5
2 1

Sample Output 3

-1
1
0
1
0