BFS Shortest Path Length

As the BFS algorithm starts from one node and gradually expands to the neighbors, it’s possible to find the shortest path from the starting node to all the other nodes in the graph. We need to modify the initial algorithm a bit to do that. We will have a distance array d, which will have all the values set to -1 initially. If the value of a vertex is -1, then the vertex isn’t visited yet. If the value is positive, the value represents the distance of the current vertex from the starting point:
from collections import deque

n, e = map(int, input().split())        # n: vertices, e: edges
g = [[] for _ in range(n)]              # graph - adjacency list

for _ in range(e):                      # read edges
    a, b = map(int, input().split())    # a -> b and b -> a
    g[a].append(b)
    g[b].append(a)

start = int(input())                    # start vertex
d = [-1] * n                            # distance from start 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
            q.append(to)                # add vertex to queue

print(d)
Here we first initialize the distance array d with -1s. This acts as an indication that none of the vertices were used yet. Then we set the value of d[start] to 0, which means that the distance from the vertex start to start is 0.
As the algorithm processes more nodes, their corresponding values are updated in the distance array d, giving us all the distance values for all the nodes starting from the vertex start.
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
  1. d = [-1, -1, -1, 0], q = [3]
  1. v = 3, q = [] β†’ add all the neighbors that are not used to the queue
  1. d = [-1, -1, 1, 0], q = [2]
  1. v = 2, q = [] β†’ add all the neighbors that are not used to the queue
  1. d = [2, 2, 1, 0], q = [0, 1]
  1. v = 0, q = [1] β†’ 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. Done
n = 5, e = 4
The input a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 4)]
The starting vertex is 0
  1. d = [0, -1, -1, -1, -1], q = [0]
  1. v = 0, q = [] β†’ add all the neighbors that are not used to the queue
  1. d = [0, 1, 1, -1, -1], q = [1, 2]
  1. v = 1, q = [2] β†’ add all the neighbors that are not used to the queue
  1. v = 2, q = [] β†’ add all the neighbors that are not used to the queue
  1. Done
    1. Notice how nodes 3 and 4 were never visited.
      They were not connected to the initial node 0.

Challenge: Find the Shortest Path Length

Given an undirected graph with v vertices and e edges, you are asked to calculate the shortest path between vertex 1 and vertex v. If they are not connected, the program should print Impossible.

Input

The first line of the input contains two integers v (1 ≀ v ≀ 100 000) and e (1 ≀ e ≀ 100 000).
The following e lines contain pairs of integers v1, v2 (1 ≀ v1, v2 ≀ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

Output

The program should print the length of the shortest path between 1 and v

Examples

Input
Output
5 6 1 2 2 3 1 3 3 4 4 3 3 5
2
2 1 1 2
1
2 0
Impossible
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in