Restore the Hanging Binary Tree Model

Little Y is a crafty OIer who owns many binary tree models. In her favorite model, each node has a unique identifier. Originally, she hung the tree on the wall with the root at the top and the left and right subtrees hanging to the left‐bottom and right‐bottom, respectively. Moreover, she arranged the tree in such a way that the inorder traversal (i.e. traversing the left subtree, then the node, then the right subtree) produces the lexicographically smallest sequence possible among all choices of hanging. (In other words, if the inorder traversal yields the sequence \(a_1, a_2, \dots, a_n\), then for any other valid hanging the sequence is not lexicographically smaller than \(a_1, a_2, \dots, a_n\); here lexicographical order is defined in the usual way.)

One unfortunate day the model fell from the wall. Although none of the nodes or edges were damaged, Little Y can no longer recall which node was originally the root. She is now busy with her Tsinghua training camp preparations and has turned to you for help in restoring her binary tree model. Your task is to determine the hanging (by selecting a root and assigning for each node which child hangs on the left and which on the right) that yields the lexicographically smallest inorder traversal sequence, and then output that inorder sequence.

Note: The tree is given as an undirected graph with \(n\) nodes and \(n-1\) edges. When a node is chosen as root, the tree is oriented: the parent is removed from its neighbor list. Hence, every node except the root will have at most two children. You are allowed to choose for each node with one child whether to hang the child on the left or on the right, and for nodes with two children, you may swap the left and right subtrees. The optimal choices should ensure that the overall inorder sequence (i.e. the concatenation of the inorder sequences of the left subtree, the current node, and the right subtree) is lexicographically minimal.

Formally, if a node \(u\) with children \(L\) and \(R\) (after choosing an orientation) yields inorder sequence \[ S(u)=\begin{cases} [u], & \text{if } u \text{ is a leaf};\\ \min\{S(child)+[u], [u]+S(child)\} & \text{if } u \text{ has one child};\\ \min\{S(L)+[u]+S(R),\; S(R)+[u]+S(L)\} & \text{if } u \text{ has two children}, \end{cases} \] then among all possible choices of a root and assignments of left/right children the one with the lexicographically smallest\(S(root)\) should be chosen. (A sequence \(X = x_1,x_2,\dots,x_n\) is lexicographically smaller than \(Y = y_1,y_2,\dots,y_n\) if there exists an index \(i\) such that \(x_1=y_1,\,x_2=y_2,\,\dots,\,x_{i-1}=y_{i-1}\) and \(x_i < y_i\).)

inputFormat

The input begins with a line containing a single integer \(n\) (where \(n \ge 2\)) representing the number of nodes in the tree. Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) which indicate that there is an edge between nodes \(u\) and \(v\). It is guaranteed that the given graph is a tree that can be oriented as a binary tree (i.e. when any node is chosen as the root, each node will have at most two children).

outputFormat

Output a single line containing the inorder traversal sequence (i.e. the lexicographically smallest sequence under an optimal hanging) as space‐separated node identifiers.

sample

3
1 2
1 3

1 2 3