Problem Description

In a certain city, there are $ N $ villages numbered from village $ 1 $ to village $ N $. Village $ i $ is located at elevation $ H_i $. No two villages are at the same elevation.
There are $ M $ waterways connecting pairs of villages, where the $ i $-th waterway connects village $ A_i $ and village $ B_i $. Waterways are only passable from the higher-elevation village to the lower-elevation village.
In this city, $ K $ villages, namely $C_1, C_2, C_3, \dots, C_K$, have been designated as shelters in case of disasters.
For all $ N $ villages, determine whether it is possible to reach any shelter using zero or more waterways, and if possible, find the minimum number of waterways needed to reach a shelter.

Input Format

The input is given from the 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 Format

Output $ N $ lines. On the $ i $-th line, output the minimum number of waterways needed to reach any shelter from village $ i $, or -1 if it is not possible to reach any shelter.

Sample Input and Output

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

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

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

Notes/Hints

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 inputs are integers

Sample Explanation 1

• Village $ 1 $: Since village $ 1 $ itself is designated as a shelter, the minimum number of waterways used is $ 0 $.
• Village $ 2 $: Since village $ 2 $ itself is designated as a shelter, the minimum number of waterways used is $ 0 $.
• Village $ 3 $: Since village $ 3 $ is higher in elevation than village $ 1 $, it can move to village $ 1 $ designated as a shelter using the 2nd waterway. The number of waterways used is $ 1 $, which is the minimum.
• Village $ 4 $: Since village $ 4 $ is higher in elevation than village $ 2 $, it can move to village $ 2 $ designated as a shelter using the 3rd waterway. The number of waterways used is $ 1 $, which is the minimum.
• Village $ 5 $: It can move to village $ 3 $ using the 5th waterway, and then to village $ 1 $ designated as a shelter using the 2nd waterway. The number of waterways used is $ 2 $, which is the minimum.

Sample Explanation 2

From village $ 5 $, it is not possible to move anywhere, and village $ 5 $ itself is not designated as a shelter, so output -1 on the 5th line.

见题面 Input 部分

见题面 Output 部分