QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB
[0]

# 9713. Kill the tree

Statistics

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)=vTd(w,v). We call a vertex w on tree T the critical point, if c(w)min

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