촌수계산

 

 

bfs

1.양방향 연결로 인접배열 생성! 

2. 출발촌수에서 최소한으로 도착촌수에 가는 단계를 구한다

3.연결되어있지 않으면 -1

 

N = int(input())
a, b = map(int,input().split())
M = int(input())
adj = [[] for _ in range(N+1)]
visited = [0] * (N+1)

def bfs(start):
    cnt = 0
    queue = [start]
    while queue:
        t = queue.pop(0)
        if t == b:
            return visited[t]
        for i in adj[t]:
            if visited[i] == 0:
                queue.append(i)
                cnt += 1
                visited[i] = visited[t] + 1
    return -1



for _ in range(M):
    v1,v2 = map(int,input().split())  # 연결관계
    adj[v1].append(v2)
    adj[v2].append(v1)


print(bfs(a))