# Practice on Toph

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

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

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

90% Solution Ratio

MujahidEarliest,

samnoon_baiustFastest, 0.3s

samnoon_baiustLightest, 35 MB

Jewel.SamaCShortest, 772B

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