Shortest Path?

Peregrine_Falcon Criterion 2021 Round 9
Limits 1s, 256 MB

Given an unweighted, undirected and connected graph consists of $N$ nodes numbered from $1$ to $N$. Total $M$ edges connecting the nodes.

There is a source node $S$ and a target node $T$. Let's say there are total $G$ nodes in any shortest path(s) from node $S$ to $T$. You have to perform $Q$ independent queries on this graph. For each query, you will be given a node $X$.

You have to find the minimum distance from $X$ to any of the $G$ nodes.

Input

The first line of the input will contains three space-separated integers $N$, $M$ and $Q$ $(3 ≤ N, M, Q ≤ 5×10^5)$, the number of nodes, the number of edges and the number of queries respectively.

Each of the next $M$ lines contains two space separated integers $U$ and $V$ $(1 ≤ U, V ≤ N, U != V)$ meaning there is an edge connecting node $U$ and $V$.

Next line contains two space separated integers $S$ and $T$ $(1 ≤ S, T ≤ N)$ denoting the source and target nodes respectively.

Next $Q$ lines will describe the queries. For each query, you will be given an integer $X$ $(1 ≤ X ≤ N)$.

Output

For each query, print the answer in a line in the same order in which the queries appear in the input.

Sample

InputOutput
7 7 3
1 2
1 3
2 4
3 4
3 5
4 7
4 6
1 6
5
6
7
1
0
1

There are two shortest paths from node 1 to 6.
First shortest path consists of node 1 → 2 → 4 → 6.
Second shortest path, 1 → 3 → 4 → 6.
So, there are total 5 nodes that is in any shortest path from node 1 to 6. They are node 1, 2, 3, 4, and 6.
In first query, from node 5, node 3 is closest with distance 1.
In second query, node 6 is already in the list. So, answer is 0.
In third query, node 4 is reachable from node 7 with distance 1.


Submit

Login to submit.

Contributors

Statistics

88% Solution Ratio
MujahidEarliest, Feb '21
user.953511Fastest, 0.2s
user.953511Lightest, 34 MB
Jewel.SamaCShortest, 772B
Toph uses cookies. By continuing you agree to our Cookie Policy.