Minimizing the Longest Path in a Directed Tree

You are given a tree with \(N\) nodes and \(N-1\) undirected edges. For any assignment of directions to these edges, the cost of the resulting directed graph is defined as the length of its longest path (i.e. the maximum number of consecutive edges in any directed path). Your task is to choose a direction for each edge so that the cost is minimized, and output one valid orientation scheme.

Hint: Since every tree is bipartite, you can partition the nodes into two sets based on parity of their distance from an arbitrary root. Then, if you direct all edges from the even-level nodes to the odd-level nodes, any directed path will have a length of at most \(1\).

In other words, if we let \(level(u)\) be the parity (even/odd) of the distance of a vertex \(u\) from a fixed root (say node 1), for each edge \((u,v)\) (which always connects nodes of different parity), direct the edge from the node with even level to the node with odd level.

Your answer should implement this strategy.

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 10^5\)), the number of nodes in the tree.

The following \(N-1\) lines each contain two space-separated integers \(u\) and \(v\) (\(1 \leq u,v \leq N\)), representing an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output \(N-1\) lines. For each edge (in the same order as input), output two space-separated integers \(a\) and \(b\) indicating that this edge is directed from node \(a\) to node \(b\). The chosen orientation must be such that every edge is directed from an even-level node to an odd-level node (when the levels are computed with respect to node \(1\)).

This ensures that the cost (i.e. the length of the longest path) of the resulting directed graph is minimized.

sample

3
1 2
2 3

1 2
3 2