树的重心

题目描述

对于树中的一点，将这个点删掉后，当前的树会分裂成许多子树构成的森林。而树的重心则是，将其删掉后，子树构成的森林中，最大的子树最小。

给定一颗包含 $n$ 个节点的树，请你求出将树的重心删掉后，子树森林中最大子树的大小。

输入格式

第一行包含一个整数 $n$，接下来 $n - 1$ 行，每行包含两个整数 $u, v$，表示这两点之间存在一条边。

数据范围： $1 \le n \le 10^5$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

样例输出 #1

4

提示

对于样例所给的树：

其中节点1为树的重心，将其删掉后构成的子树森林如下图所示：

其中最大的子树大小为4，因此答案为4。