Problem Statement

You are given a tree $T$ with $N$ vertices. The $i$-th edge connects vertices $A_i$ and $B_i$.

Construct an $N$-vertex rooted tree $R$ that satisfies the following conditions.

• For all integer pairs $(x,y)$ such that $1 \leq x < y \leq N$,
• if the lowest common ancestor in $R$ of vertices $x$ and $y$ is vertex $z$, then vertex $z$ in $T$ is on the simple path between vertices $x$ and $y$.
• In $R$, for all vertices $v$ except for the root, the number of vertices of the subtree rooted at $v$, multiplied by $2$, does not exceed the number of vertices of the subtree rooted at the parent of $v$.

We can prove that such a rooted tree always exists.

Constraints

• $1 \leq N \leq 10^5$
• $1\leq A_i,B_i \leq N$
• All values in the input are integers.
• The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

Output

Let $R$ be a rooted tree that satisfies the conditions in the Problem Statement. Suppose that the parent of vertex $i$ in $R$ is vertex $p_i$. (If $i$ is the root, let $p_i=-1$.) Print $N$ integers $p_1,\ldots,p_N$, with spaces in between.