Description

对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心

给出一棵有根树，根节点是 $1$，求这棵树的所有重心

Input Format

第一行输入一个整数 $n(2\le n\le 1E5)$ 表示有 $n$ 个节点，编号为 $1\dots n$

接下来 $n-1$ 行，每行输入两个整数 $u,v(1\le u,v\le n)$，表示 $u,v$ 之间有一条边

Output Format

每行输出一个重心

顺序由小到大

5
1 2
1 3
2 4
3 5

1

6
1 2
1 4
2 3
4 5
3 6

1
2

Source

Online Judge http://127.0.0.1