题目描述

文景的手上有一棵 $N$ 个结点的树，结点编号为 $1$ 到 $N$。

结点 $x$ 和结点 $y$ 之间的距离定义为连接两结点所需经过的最短边数。

文景决定拆除一条边，并新建另一条边，使得存在两结点之间的最远距离最大化。

请计算新建边后，距离最大的两结点间的距离。

输入格式

• 第一行包含一个整数 $N$。
• 接下来的 $N-1$ 行，每行包含两个整数 $u$ 和 $v$，表示结点 $u$ 和 $v$ 之间有一条双向边。

输出格式

输出一个整数，表示新建边后距离最大的两结点间的距离。

样例 1

4
1 2
1 3
3 4

3

样例 2

6
1 2
2 3
2 5
4 5
5 6

5

【样例解释】

对于样例 $1$，最远距离无法增加，仍然为 $3$。

对于样例 $2$，可以拆除边 $2-5$，新建边 $3-4$，最远路径为 $1-2-3-4-5-6$，其长度为 $5$。

【数据范围】

• $2 \leq N \leq 300,000$
• $1 \leq u, v \leq N$

ex_build1.in  ex_build1.out  ex_build2.in  ex_build2.out  ex_build3.in  ex_build3.out