2644번: 촌수계산 (그래프, BFS)

www.acmicpc.net/problem/2644

2644번: 촌수계산

# 촌수계산
# https://www.acmicpc.net/problem/2644 (그래프, BFS)

from collections import deque


def bfs(graph, st, ed):
    visited = []
    queue = deque([(st, 0)])

    while queue:
        v, cnt = queue.popleft()
        if v in visited:
            continue

        visited.append(v)
        if v == ed:
            return cnt

        for e in graph[v]:
            if e not in visited:
                queue.append((e, cnt + 1))

    return -1


n = int(input())
st, ed = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}

r = int(input())
for _ in range(r):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

cnt = bfs(graph, st, ed)
print(cnt)