2021번: 최소 환승 경로

2021번: 최소 환승 경로

 

import sys
from collections import deque, defaultdict

r = sys.stdin.readline

node_num, flag_num = map(int, r().split())
graph = defaultdict(set)

for i in range(1, flag_num + 1):
    temp = list(map(int, r().split()))
    temp.pop()
    for node in temp:
        graph[node].add(i + node_num)
        graph[i + node_num].add(node)

start, end = map(int, r().split())
q = deque([])
q.append(start)
visited = set()
visited.add(start)
cost = {start: 0}
while q:
    cur_node = q.popleft()
    if cur_node == end:
        break

    for adj in graph[cur_node]:
        if adj not in visited:
            if adj >= node_num + 1:
                cost[adj] = cost[cur_node]
            else:
                cost[adj] = cost[cur_node] + 1
            visited.add(adj)
            q.append(adj)

if start == end:
    print(0)
else:
    print(cost[end] - 1 if end in cost else -1)