AT_past202012_i 避難計画

[problemUrl]: https://atcoder.jp/contests/past202012-open/tasks/past202012_i ある都市には村が $ 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 $ 本以上の水路を使っていずれかの避難所に辿りつくことができるか、できるなら最小で何本の水路を通ればよいかを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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` を出力せよ。

### 注意 この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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) $ - 入力は全て整数 ### Sample Explanation 1 \- 村 $ 1 $ : 村 $ 1 $ 自身が避難所に指定されているので、使用する水路の最小の本数は $ 0 $ です。 - 村 $ 2 $ : 村 $ 2 $ 自身が避難所に指定されているので、使用する水路の最小の本数は $ 0 $ です。 - 村 $ 3 $ : 村 $ 3 $ の方が村 $ 1 $ より標高が高いので、$ 2 $ 番目の水路を使って避難所に指定されている村 $ 1 $ に移動することができます。使う水路の本数は $ 1 $ で、これが最小です。 - 村 $ 4 $ : 村 $ 4 $ の方が村 $ 2 $ より標高が高いので、$ 3 $ 番目の水路を使って避難所に指定されている村 $ 2 $ に移動することができます。使う水路の本数は $ 1 $ で、これが最小です。 - 村 $ 5 $ : $ 5 $ 番目の水路を使って村 $ 3 $ に移動し、更に $ 2 $ 番目の水路を使って避難所に指定されている村 $ 1 $ に移動することができます。使う水路の本数は $ 2 $ で、これが最小です。 ### Sample Explanation 2 村 $ 5 $ からはどこにも行くことができず、村 $ 5 $ 自身が避難所に指定されていることもないので、$ 5 $ 行目には `-1` を出力します。