Lexicographically Smallest Preorder Traversal of a Modified Binary Tree

You are given a binary tree with n nodes (numbered from 1 to n) with node 1 as the root. The tree is given in the following format: for each node i from 1 to n, two integers are provided representing the left and right children of node i (a value of 0 indicates that the child is missing).

The preorder traversal of a binary tree is defined in \(\textbf{latex}\) as:

[ \text{Preorder}(\text{tree}) = \begin{cases} \emptyset, & \text{if the tree is empty},\[6mm] {\text{root}} \oplus \text{Preorder}(\text{left subtree}) \oplus \text{Preorder}(\text{right subtree}), & \text{otherwise}, \end{cases} ]

You are allowed to perform the following operation at most once:

• Choose one node \(u\) (other than the root) and disconnect it from its parent. Then, reattach \(u\) (with its entire subtree) as a child of another node \(v\) (\(v \neq u\)) in a vacant child slot (either left or right) such that the resulting structure is still a binary tree with node 1 as the root. In other words, after the operation, every node has at most two children and there is no cycle.

Your goal is to obtain a tree whose preorder traversal sequence (i.e. the sequence of node numbers visited) is lexicographically smallest possible. Output this lexicographically smallest preorder sequence as a sequence of node numbers separated by a space.

inputFormat

The first line contains an integer n (the number of nodes, \(n \ge 1\)).

Then follow n lines. The i-th line (1-indexed) contains two integers l_i and r_i, representing the left and right child of node i respectively. A value of 0 indicates a missing child.

You can assume that the given tree is valid and node 1 is the root.

outputFormat

Output one line containing the lexicographically smallest preorder traversal sequence of the tree after performing at most one valid operation. The numbers should be separated by a single space.

sample

3
2 3
0 0
0 0

1 2 3