[백준 2644 촌수 계산] 파이썬

# 2644 촌수계산
# BFS
# 파이썬 56 ms
 
N = int(input())                    # 사람 수 
A, B  = map(int, input().split())   # 타겟 
T  = int(input())                   # 관계 수
graph = [[]for i in range(N+1)]     # 관계를 저장하기 위한 그래프
info = [0]*(N+1)                    # Start -> End로 걸리는 거리를 기록
 
for i in range(T):      # 그래프 저장
    P, C = map(int, input().split())
    graph[P].append(C)
    graph[C].append(P)
 
 
 
def bfs(start, end):    # 시작부터 끝까지 탐색
    queue = [start]
    visited = []
    
    while queue:
        vtx = queue.pop(0)
        visited.append(vtx)
        if vtx==end:
            break
 
        for c in graph[vtx]:
            if c not in visited:
                info[c] = info[vtx] + 1
                queue.append(c)
 
 
    if info[end]==0:
        print(-1)
    else:
        print(info[end])
 
bfs(A,B)