Given an unweighted, undirected and connected graph consists of
$N$ nodes numbered from
$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
$T$. You have to perform
$Q$ independent queries on this graph. For each query, you will be given a node
You have to find the minimum distance from
$X$ to any of the
The first line of the input will contains three space-separated integers
$(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
$(1 ≤ U, V ≤ N, U != V)$ meaning there is an edge connecting node
Next line contains two space separated integers
$(1 ≤ S, T ≤ N)$ denoting the source and target nodes respectively.
$Q$ lines will describe the queries. For each query, you will be given an integer
$(1 ≤ X ≤ N)$.
For each query, print the answer in a line in the same order in which the queries appear in the input.
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.