트리의 부모 찾기

루트가 정해지지 않은 트리가 주어진다. 이 트리의 루트를 1번 노드로 정했을 때, 1번을 제외한 각 노드의 부모 노드 번호를 구하는 프로그램을 작성하시오.

어떤 노드의 부모는 루트에서 그 노드까지 가는 경로에서 바로 앞에 오는 노드이다.

첫째 줄에 노드의 개수 $N$ ($2 \le N \le 100\,000$)이 주어진다. 노드에는 1번부터 $N$번까지 번호가 붙어 있다.

둘째 줄부터 $N-1$개의 줄에 트리에서 연결된 두 노드의 번호가 공백을 사이에 두고 주어진다. 입력으로 주어지는 그래프는 항상 트리이다.

$N-1$개의 줄을 출력한다. 2번 노드부터 $N$번 노드까지 순서대로, 각 노드의 부모 노드 번호를 한 줄에 하나씩 출력한다.