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.
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)$
.
For each query, print the answer in a line in the same order in which the queries appear in the input.
Input | Output |
---|---|
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. |