题目背景

$\text{POJ}$ $1655$改编

题目描述

一颗 $n$ 个节点的无根树，编号 $1$ ~ $n$，找到一个节点 $x$，使其满足：$x$ 为根时，最大子树的节点数最少。$(1≤n≤10^6)$

最大子树即结点数最多的子树。

格式

输入格式

第一行一个正整数 $n$；

以下 $n-1$行，每行两个正整数 $u,v$，用空格隔开，表示 $u,v$ 两个结点有边相连。

输出格式

一个正整数 $x$，表示树的重心，如果有多个结点满足条件，请输出编号最小的结点。

样例1

样例输入1

7
2 6
1 2
1 4
4 5
3 7
3 1

样例输出1

1

限制

时间：$1s$ 空间：$256M$

对于 $100\%$ 的数据：$1≤n≤10^6$；

来源

地址：$zloj,J2021$域
作者：$jialiang2509$
模拟赛$T3$

地址：$zloj,J2020$域
作者：$jialiang2509$
模拟赛$T1$