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)=∑v∈Td(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