There are $n$ cities and $m$ roads. Each road is bidirectional and connects two cities. It is also known that $k$ cities have an anime shop.

If you live in a city, you of course know the local anime shop well if there is one. You would like to find the nearest anime shop that is not in your city.

For each city, determine the minimum distance to another city that has an anime shop.

Input

The first line has three integers $n$, $m$ and $k$: the number of cities, roads and anime shops. The cities are numbered $1,2,\dots,n$.

The next line contains $k$ integers: the cities that have an anime shop.

Finally, there are $m$ lines that describe the roads. Each line has two integers $a$ and $b$: there is a road between cities $a$ and $b$.

Output

Print $n$ integers: for each city, the minimum distance to another city with an anime shop. If there is no such city, print $-1$ instead.

Example

Input:

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

Output:

1 1 1 1 -1 1 -1 2 -1

Subtask 1 (23 points)

• $1 \le k \le n \le 1000$
• $0 \le m \le 2000$

Subtask 2 (16 points)

• $1 \le k \le n \le 10^5$
• $m=n-1$
• Each road is between cities $i$ and $i+1$ for $i=1,2,\dots,n-1$

Subtask 3 (61 points)

• $1 \le k \le n \le 10^5$
• $0 \le m \le 2 \cdot 10^5$