哨兵

题目描述

王国里有 n 个城市，用 n-1 条道路把它们连起来（也就是一棵树，每两城之间只有一条路）。 现在要在城市里放三组哨兵 A、B、C，同一个城市可以放多组。

要求：A 到 B 的距离 = A 到 C 的距离。在满足这个条件的前提下，让 B 到 C 的距离尽量大。问这个最大距离是多少。

输入格式

第一行：一个正整数 n。 接下来 n-1 行：每行两个整数 \(u_i v_i\)，表示城市 \(u_i\) 与 \(v_i\) 有一条路相连（双向）。

输出格式

输出一个整数：满足条件时 B 到 C 的最大距离（单位是"经过的边数"）。

输入输出样例 #1

输入 #1

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

输出 #1

4

说明/提示

【样例说明】 可以有一种放法：把 A 放在 5，B 放在 3，C 放在 7，能满足 A 到 B 与 A 到 C 等距，此时 B 到 C 的距离为 4，并且这是能做到的最大值。

【评测用例规模与约定】

• 对于 20% 的评测用例：\(1 \le n \le 500\)
• 对于所有评测用例：\(1 \le n \le 5000，1 \le u_i, v_i \le n\)