Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shortest Path?

By Peregrine_Falcon · Limits 1s, 256 MB

Given an unweighted, undirected and connected graph consists of NN nodes numbered from 11 to NN. Total MM edges connecting the nodes.

There is a source node SS and a target node TT. Let's say there are total GG nodes in any shortest path(s) from node SS to TT. You have to perform QQ independent queries on this graph. For each query, you will be given a node XX.

You have to find the minimum distance from XX to any of the GG nodes.

Input

The first line of the input will contains three space-separated integers NN, MM and QQ (3N,M,Q5×105)(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 MM lines contains two space separated integers UU and VV (1U,VN,U!=V)(1 ≤ U, V ≤ N, U != V) meaning there is an edge connecting node UU and VV.

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

Next QQ lines will describe the queries. For each query, you will be given an integer XX (1XN)(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.


Discussion

Statistics


91% Solution Ratio

MujahidEarliest, 4M ago

samnoon_baiustFastest, 0.3s

samnoon_baiustLightest, 35 MB

Jewel.SamaCShortest, 772B

Submit

Login to submit

Editorial

First, we need to find out which nodes are part of any of the shortest path(s). We need to run a BFS...

Related Contests