Given a tree with $N$ vertices(vertices are numbered from $1$ to $N$), where 1 is the root of the tree. The weight of the edges on the tree is 1.

Define $d(u, v)$ as the distance between vertex $u$ and $v$.

Define $c(w)=\sum \limits_{v \in T} d(w, v)$. We call a vertex $w$ on tree $T$ the critical point, if $c(w) \le \min \limits_{u \in T} c(u)$

Now, for all $i \in [1, N]$, you must print the "critical points" of the subtree rooted at vertex $i$.

Input

The first line of the input contains an integer $N$ denotes the number of vertices of the tree.

Then, $N - 1$ line follows, the $i^{th}$ line contains two integers $a_i, b_i$, denotes the $i^{th}$ edge on the tree.

• $1 \le N \le 2 \times 10^5$
• $1 \le a_i, b_i \le N$
• The input is a tree

Output

Output $N$ lines.

On the $i^{th}$ line, output the "critical points" of the subtree rooted at vertex $i$ in ascending order. Two integers in one line must be separated by one space.

Sample Input

4
1 2
2 3
2 4

Sample Output

2
2
3
4