The contest is ended. New submissions will be treated as correction submissions and will not be counted in the contest.

题目描述

所谓的山，是一种上细下粗的结构。能不能在「树」里也找到这样的结构呢？

给定一个以 $1$ 为根的大小为 $n$ 的有根树 $T$。你需要找到满足宽度单调不减的导出子树中最大的一棵：

• 记该导出子树为 $T_0$，共有 $k$ 层。
• 记 $T_0$ 的根节点的深度为 $1$，计算出 $T_0$ 中每个结点的深度 $d_i$。由此定义 $T_0$ 第 $i$ 层的宽度 $w_i$ 为「所有深度为 $i$ 的节点的个数」。
• 你需要使得 $w_i$ 单调不减。即，$w_1\le w_2\le \cdots \le w_k$。

记原树的点集和边集分别为 $V,E$。导出子树是原树的一个连通块，它的点集 $V_0\subseteq V$，边集 $E_0$ 是 $E$ 当中所有端点均在 $V_0$ 内的边。导出子树的根，是组成它的所有节点中在原树内深度最浅的那一个。$T$ 也可以被认为是自身的一棵导出子树。

如图所示，绿色的区域和橙色的区域分别是原树的导出子树。它们的根分别为 $2$ 和 $13$。

注意：导出子树的定义略微不同于子树的定义。请不要将两者混淆。

请找到最大的符合条件的导出子树的大小。

输入格式

第一行一个正整数 $n$，表示整棵树的大小。

接下来 $n-1$ 行，每行两个整数 $u,v$，描述树上的一条边。

输出格式

输出共一行一个整数，表示最大的符合条件的导出子树的大小。

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

9

17
1 2
2 3
3 4
4 5
4 6
3 7
7 8
7 9
7 10
2 11
2 12
1 13
13 14
14 15
14 16
13 17

16

提示

样例解释

如图所示，标灰的节点是两个样例中选出来的导出子树。

• 样例 $1$ 找到的导出子树，每一层的宽度分别为 $\{1,2,3,3\}$。
• 样例 $2$ 找到的导出子树，每一层的宽度分别为 $\{1,2,4,4,5\}$。

数据范围及约定

对于全部数据，$1\le n\le 5\times 10^5$。