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 $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.


Discussion

Statistics


90% Solution Ratio

MujahidEarliest, 4w 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 $B...

Related Contests