最长回路

时间限制:1s

空间限制:64MB

题目描述

现有编号为\(1\) ~ \(n\)的\(n\)个城市，有\(n-1\)条 双向 交通道路使得任意两个城市之间连通，即：它们形成了一棵树的结构。

你可以进行一次下列操作：

选择两个城市，如果他们之间没有交通道路连接，你可以在它们之间建立一条 双向 交通道路。

然后从中选择一条满足条件的路径：

①路径的起点和终点一致，即：该路径是回路

②路径中，相同的交通道路只能经过一次。

我们记路径中所经过的交通道路数量为 回路的长度 ，请合理地建设道路，并求回路长度的最大值。

输入格式

第一行一个整数\(n\)，表示城市数量

接下来\(n-1\)行，每行两个整数\(u,v\)，表示\(u,v\)之间有一条双向边。

输出格式

一个整数，表示最长回路的长度。

样例输入1

3
1 2
2 3

样例输出1

3

样例1解释

在城市\(1,3\)之间建立交通道路，则路径\(1\to2\to3\to1\)满足条件，它的长度是\(3\)

样例输入2

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

样例输出2

8

样例输入3

31
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31

样例输出3

9

数据范围及限制

\(3\le n\le 30000\)

保证给出的关系是一棵树，不会出现重边、自环。