14591459 SUSTech Online Judge
Problem 1459 --Critical Node

1459: Critical Node

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 137  Solved: 49
[Submit][Status][Web Board]

Description

Given a tree \(T\) whose nodes are numbered from 1 to \(n\) and the root of the tree is node 1. Define \(dis(x, y)\) as the distance between node \(x\) and node \(y\) (i.e., the least number of edges in the path from node \(x\) to node \(y\)).

Then define \(k(w)=\sum \limits_{v \in T} dis(w, v)\). We call a node \(w\) on tree \(T\) the critical node if and only if \(k(w)≤\min \limits_{u\in T}k(u)\). You are asked to print all the critical nodes of the subtree rooted at node \(i\) for \(i \in [1,n]\).

Input

The first line contains an integer \(n\) \((1\le n \le 200\ 000)\), indicating the number of nodes of the tree \(T\).

Then \(n-1\) lines follow. Each line contains two integers \(u,v\) \((1\le u,v \le n)\) describing an edge, indicating the indexes of vertexes that connect an edge.

Output

Output \(n\) lines.

On the \(i^{th}\) line, output all the critical nodes of the subtree rooted at node \(i\) in ascending order. Multiple 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

HINT

Source

 

[Submit][Status]