트리의 부모 찾기

• 1번 노드에서부터 전체 트리를 탐색하면서 방문하는 노드들에 대해 이전 노드를 부모 노드로 마킹하면 끝.
• DFS/BFS 어느 것을 사용해도 상관 없다. 내 경우는 DFS를 사용.

"""Solution code for "BOJ Q11725. 트리의 부모 찾기".

- Problem link: https://www.acmicpc.net/problem/11725
- Solution link: http://www.teferi.net/ps/problems/boj/11725
"""

import sys


def main():
    N = int(sys.stdin.readline())
    graph = [set() for _ in range(N)]
    for _ in range(N - 1):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        graph[u - 1].add(v - 1)
        graph[v - 1].add(u - 1)

    parent_by_node = [None] * N
    stack = [0]
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if parent_by_node[v] is None:
                stack.append(v)
                parent_by_node[v] = u + 1

    print(*parent_by_node[1:], sep='\n')


if __name__ == '__main__':
    main()