题目描述

给定一棵包含 $n$ 个节点的树（节点编号 $1\sim n$）。每条边的长度都是 $1$。求树的重心 $x$（比起其他的点，以 x 为根节点时的最大子树最小）。

输入格式

第一行一个整数 $n$。
接下来 $n-1$ 行，每行包括两个整数 $u,v$ ，表示节点 $u$ 与节点 $v$ 之间有一条边。

输出格式

一行一个整数 $x$。如果有多个重心，输出编号最小的一个。

6
1 2
2 3
3 4
4 5
5 6

3

数据规模与约定

对于 $100\%$ 的数据，$0 < n \le 10^3$。