"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/132266
"""

# lv3 부대 복귀
# 내 풀이
# 조건
# 각 부대 지역 고유번호 지정
# 임무 완료 후 최단 시간으로 부대 복귀
# 적군의 방해로 지역이 막혀 부대 복귀 불가능한 대원 발생 가능

# 접근 사고 방향
# 최단 거리를 구하는 조건이라 다익스트라 알고리즘 떠올려야 하나 익숙하지 않아 dfs로 1차 접근
# dfs 방문 여부로 인한 최단거리 구성의 어려움으로 인한 bfs로 선회 후 재구성:
# >1차: 시간초과 발생

# 2차 생각 전환
# 방향전환: 꼭 출발점에서 목적지를 찾아가야하나? 목적지에서 시작점까지를 돌면 source마다 할 필요 없이 반복 필요 없음
# 도착점에서 갈 수 없는 곳 모두 -1로 생각!
# 목표:최단 시간을 담은 값을 리턴


# 총 지역수: n , 길 정보 roads , 부대원 위치: sources 강철부대 지역:destination

from collections import deque
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)  # 최대 깊이 설정

m = defaultdict(list)


def solution(n, roads, sources, destination):
    check = [-1 for _ in range(n + 1)]  # 각 부대별 최단 거리 정리 # 도착점으로부터 시작으로 사고 전환! 도착 못하면 -1
    result = []

    r = roads
    s = sources
    d = destination

    # 위치별 정리
    for i, j in r:
        m[i].append(j)
        m[j].append(i)

    v = [False for _ in range(n + 1)]  # 방문 여부

    q = deque([[d, 0]])

    new = []  # 거리에 따라 추가할 부분

    while q:
        x, t = q.popleft()

        v[x] = True  # 방문

        check[x] = t

        new += m[x]

        if len(q) == 0:
            new = list(set(new))  # 중복 제거

            if len(new) == 0:
                break

            for u in [y for y in new if v[y] == False]:
                q.append([u, t + 1])

            if len(q) == 0:
                break

            new = []  # 그 다음 순서를 담기 위해서 초기화!!

    for z in s:
        result.append(check[z])


    return result