Given an unweighted, undirected and connected graph consists of nodes numbered from to . Total edges connecting the nodes.
There is a source node and a target node . Let's say there are total nodes in any shortest path(s) from node to . You have to perform independent queries on this graph. For each query, you will be given a node .
You have to find the minimum distance from to any of the nodes.
The first line of the input will contains three space-separated integers , and , the number of nodes, the number of edges and the number of queries respectively.
Each of the next lines contains two space separated integers and meaning there is an edge connecting node and .
Next line contains two space separated integers and denoting the source and target nodes respectively.
Next lines will describe the queries. For each query, you will be given an integer .
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.
Login to submit
First, we need to find out which nodes are part of any of the shortest path(s). We need to run a BFS...