Finding the Nearest Anime Shop

You are given an undirected unweighted graph with n cities and m two‐way roads connecting them. Additionally, among these n cities, k cities have an anime shop.

For each city, compute the minimum distance to any different city that has an anime shop. In other words, if the city itself has an anime shop, its own shop does not count; you must find the nearest anime shop in another city.

If no such city exists (i.e. the city is isolated from any other anime shop), output -1 for that city.

Note: The distance is defined as the number of roads on the shortest path.

The problem involves finding not only the closest anime shop for cities without a shop but also, for cities that have an anime shop, finding the second closest anime shop (i.e. the closest one among those with a shop that is not itself).

The formulas used in this problem are given in \( \LaTeX \) as follows:

For a city \( i \), let \( d(i, j) \) be the number of roads in the shortest path between cities \( i \) and \( j \). If city \( i \) itself hosts an anime shop, then the answer for that city is \[ answer(i)=\min_{\substack{j \in S \\ j\neq i}}\; d(i, j), \] where \( S \) is the set of cities with an anime shop. For a city without an anime shop, the answer is: \[ answer(i)=\min_{j \in S}\; d(i, j). \] If no path exists, the answer is defined to be \( -1 \).

inputFormat

The first line contains three integers n, m, and k (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 10^5\), \(1 \leq k \leq n\)).

Then m lines follow, each containing two integers u and v (\(1 \le u, v \le n\)), representing a bidirectional road between cities u and v.

The next line contains k distinct integers indicating the indices of the cities that have an anime shop.

outputFormat

Output a single line with n space-separated integers. The i-th integer should be the minimum distance from city i to a different city that has an anime shop. If such a city does not exist, output -1 for that city.

sample

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

1 2 1 1 2