Challenge: Fewest Roads

Lab Python Intermediate 20 points

Read a graph, then a start and a goal. Print the smallest number of roads needed to get from start to goal using BFS, or -1 if it can't be reached.

Input

Line 1: n m – the number of places (numbered 0 to n − 1) and the number of roads. Then m lines a b: a two-way road between a and b.

Last line: start goal.

Output

One number.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

dist starts as -1 everywhere except dist[start] = 0.

When you first reach w from v, dist[w] = dist[v] + 1.

Solution explanation

BFS reaches every place first along a path with the fewest roads.

Show solution

from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
s, t = map(int, input().split())
dist = [-1] * n
dist[s] = 0
q = deque([s])
while q:
    v = q.popleft()
    for w in g[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            q.append(w)
print(dist[t])

Output

Answer