Problem G: Critical Node ## Problem G: 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

[Submit][Status]