Pondo Euler Tour

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

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

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

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

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