Finding Parents in a Tree

A tree with no designated root is given. Take node 1 as the root, then find the parent of every node other than node 1.

The parent of a node is the node that comes immediately before it on the path from the root to that node.

The first line contains the number of nodes $N$ ($2 \le N \le 100\,000$). The nodes are numbered from 1 to $N$.

Each of the next $N-1$ lines contains the numbers of two nodes joined by an edge, separated by a space. The given graph is always a tree.

Print $N-1$ lines. Print the parent of each node, one per line, in order from node 2 to node $N$.