트리의 부모 찾기

첫 줄에 노드의 개수 n (2 이상 5000 이하) 이 주어집니다. 이어서 n-1개의 줄에 트리의 간선 u v 가 주어집니다. 노드 번호는 1번부터 n번까지입니다.

트리의 루트를 1번 노드로 할 때, 2번부터 n번까지 각 노드의 부모 노드 번호를 한 줄에 하나씩 순서대로 출력하세요.

예시

입력

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

출력

4
6
1
3
1
4