Give a binary tree which has ~N~ nodes, print all nodes of the tree in the pre order (root, left, right). The nodes are numbered from ~1~ to ~N~. The root of the tree is ~1~.

Input

• The first line contains the number of nodes of a tree, ~N~ ~(0 < N \le 10^5)~.
• The ~i^{th}~ line of the next ~N~ lines contains two integers left and right (left, right ~\le N~), respectively, which are the left child and the right child of the ~i^{th}~ node. If left is less than or equal to ~0~, node ~i~ has no child on the left. If right is less than or equal to ~0~, node ~i~ has no right child
• The tree is guaranteed to exist

Output

• All nodes of the tree in the pre-order, separated by spaces.

Sample Input

4
2 3
0 4
0 0
0 0

Sample Output

1 2 4 3