You are given a tree with ~n~ vertices, rooted at vertex ~1~. Output the Euler tour of this tree.

Start a depth-first search at ~1~. Record a vertex when you first enter it, visit all of its children, then record it again when you leave. If a vertex has several children, visit them in increasing label order.

You only need the first and last visit of each vertex, so the tour has length ~2n~.

Input

The first line contains a single integer ~n~.

Each of the next ~n - 1~ lines contains two integers ~u~ and ~v~, denoting an undirected edge between ~u~ and ~v~.

Vertices are numbered ~1~ through ~n~. The edges form a tree.

Output

Print a single line of ~2n~ space-separated integers: the Euler tour, starting at ~1~.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le u, v \le n~ and ~u \neq v~

Example 1

Input

8
1 2
2 3
2 4
1 5
5 6
6 7
6 8

Output

1 2 3 3 4 4 2 5 6 7 7 8 8 6 5 1

Explanation

The tree, rooted at ~1~, looks like this:

      1
     / \
    2   5
   / \   \
  3   4   6
         / \
        7   8

The search enters ~1~, then visits child ~2~ before child ~5~. It records each vertex on entry and again on exit, which produces the tour above.

Example 2

Input

10
3 10
3 5
1 3
5 7
2 5
2 4
5 8
6 8
6 9

Output

1 3 5 2 4 4 2 7 7 8 6 9 9 6 8 5 10 10 3 1