10098 트리의 부모 찾기 Silver II

문제

루트가 1인 트리가 주어질 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드 수 N (2 ≤ N ≤ 100,000)이 주어진다. 다음 N-1줄에 트리의 간선이 주어진다.

출력

2번 노드부터 N번 노드까지 부모 노드 번호를 한 줄에 하나씩 출력한다.

7
1 6
6 3
3 5
4 1
2 4
4 7

4
6
1
3
1
4