# 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