Algorithms and Data Structures

# Reconstruct the Shortest Path

When calculating the shortest path in a graph, it’s possible to also reconstruct it at the very end.
To do that, we can store the “parent” vertex for each vertex that we visit. Meaning that if we add the vertex `to` in the queue after processing the vertex `v`, we can mark that the “parent” vertex of `to` was the vertex `v`. This will allow us to reconstruct the whole path at the end. We can start from the last node in the path and then move to its parent. Then move to the parent of the current node, and so on until reaching a node that doesn’t have a parent, which will be the starting node. This can be implemented by storing an additional parent array `p`:
``````start = int(input())                    # start vertex
d = [-1] * n                            # distance from start vertex
p = [-1] * n                            # parent vertex
q = deque([start])                      # queue of vertices
d[start] = 0                            # distance from start to start is 0

while q:                                # while the queue is not empty
v = q.popleft()                     # get vertex from queue
print(v, end=' ')                   # print vertex
for to in g[v]:                     # for each vertex connected to v
if d[to] == -1:                 # if vertex is not visited
d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
p[to] = v                   # parent of vertex is v
q.append(to)                # add vertex to queue

# Reconstruction of the path from start to end
end = int(input())                      # end vertex
path = []                               # path from start to end
while end != -1:                        # while there is a parent vertex
path.append(end)                    # add vertex to path
end = p[end]                        # go to parent vertex

print(*path[::-1], sep=' -> ')          # print the path in reverse order``````
So, after adding each element to the queue, we mark its parent node in the array `p` and then reconstruct the path at the very end by moving from the last node to the first one. In the end, the path should be printed in reverse order as we were adding elements from the end of the path and analyzing parent nodes one by one until reaching the start. So, to move from start to end, we need to reverse the path.
Let’s simulate the algorithm on several inputs:
n = 4, e = 4
The input `a, b` pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]
The starting vertex is 3 and the end vertex is 0
1. `p = [-1, -1, -1, -1]`, `q = `
1. `v = 3`, `q = []` → add all the neighbors that are not used to the queue
1. `p = [-1, -1, 3, -1]`, `q = `
1. `v = 2`, `q = []` → add all the neighbors that are not used to the queue
1. `p = [2, 2, 3, -1]`, `q = [0, 1]`
1. `v = 0`, `q = ` → add all the neighbors that are not used to the queue
1. `v = 1`, `q = []` → add all the neighbors that are not used to the queue
1. Reconstruct the path
1. `end = 0``end = 2``end = 3`
1. print `3 → 2 → 0`
Notice that if the `d[end]` is still -1 by the end of the algorithm, then we were not able to actually reach the `end` vertex.

### Challenge: Find the Shortest Route

The Internet is a collection of computers that are connected to each other and can transfer data. In this case, those computers are enumerated from 1 to `n` and we know the computers that are connected to each other. Alice wants to send a message to Bob and she would want to send that message as fast as possible. So, the route should be as short as possible.
Alice has a computer with the number `a`, and Bob’s computer number is `b`. You are asked to find an optimal route of computers that would transfer the message from Alice to Bob as fast as possible.

#### Input

The first line of the input contains two integers `n` (1 ≤ n ≤ 100 000) and `e` (1 ≤ e ≤ 100 000) the number of computers and the number of connections in the network.
The next line contains two numbers `a` and `b` (1 ≤ a, b ≤ n).
The following `e` lines contain pairs of integers `c1`, `c2` (1 ≤ c1, c2 ≤ n) which means that the computer `c1` is connected to the computer `c2` and vice versa.

#### Output

The program should print the most optimal route of the message where each computer number should be separated by a space. In the case of several optimal routes, it can print any of those.

#### Examples

 Input Output 5 5 1 5 1 2 2 3 1 3 3 4 3 5 1 3 5 5 6 1 5 1 2 2 3 2 4 3 4 4 5 3 5 1 2 4 5

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB