풀이

기존에 풀던 방식으로 bfs를 사용하면서 본인의 나왔던 부모루트를 저장하면서 풀어주면 된다.

from collections import deque
import sys
n = int(input())
lst = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b  = map(int, sys.stdin.readline().split())
    lst[a].append(b)
    lst[b].append(a)
# print(lst)
visited = [0] * (n+1)
visited[1] = 1
def bfs(start):
    q = deque()
    q.append(start)
    while q:
        current = q.popleft()
        for i in lst[current]:
            if visited[i] == 0:
                visited[i] = current
                q.append(i)
bfs(1)
for i in range(2, n+1):
    print(visited[i])