Festival 1 - MarisaOJ: Marisa Online Judge

Festival 1

Time limit: 1000 ms
Memory limit: 256 MB
The Human Village can be represented by a connected graph with $n$ locations and $m$ connections. Reimu wants to organize a festival at location $n$ instead of the Hakurei Shrine as usual. There are $k$ people who want to attend the festival, and person number $i$ is currently at location $p_i$. For each person, calculate the shortest path for them to reach the festival location. ### Input - The first line contains three integers $n$, $m$, and $k$. - The second line contains $k$ integers $p_i$. - The next $m$ lines each contain two integers $u$ and $v$, representing an edge between vertices $u$ and $v$. ### Output - Print the length of the shortest path from vertex $1$ to vertex $n$. ### Constraints - $1 \le n,k \le 10^5$. - $1 \le u, v, p_i \le n$. ### Example Input: ``` 4 4 3 2 3 4 1 2 2 3 3 4 4 1 ``` Output: ``` 2 1 0 ```