题目描述

S航空公司在 $N$ 座城市之间有 $N-1$ 条航线，航线是双向的。任意两座城市都是可以互相到达的，但是可能需要在一些城市换乘不同的航线。 目前有人抱怨要到达有些城市需要换乘太多次，S航空公司为了缓解这一现状，决定取消目前的一条航线，添加另一条航线，在保证任意两座城市还是可以互相到达的前提下，使得两座城市之间需要乘坐的航线次数的最大值最小。

输入格式

第一行为一个整数 $N(4\le N \le 2500)$，表示城市的个数。城市从 $1$ 到 $N$ 编号。 接下来N-1行，每行是一对整数 $a$ 和 $b$，表示一条连接 $a$ 和 $b$ 的航线($1\le a,b\le n$)。

输出格式

输出仅一行，即航空公司进行调整后，任意两座城市之间需要乘坐的航班次数的最大值。

4
1 2
2 3
3 4

2

【样例解释】

取消3-4的航线，添加2-4的航线。

提示

对于 $100\%$ 的数据，$N\le2500$。

题目来源

没有写明来源