問題文

N 個の都市があり、それぞれの都市に 1 から N までの番号が付けられています。 また、N-1 本の道路があり、i 本目 (1 \leq i \leq N-1) の道路は都市 A_i と都市 B_i を双方向に結んでいます。 どの都市の間も、いくつかの道路を通って移動可能なものとなっています。

さて、あなたは整数 u, v (1 \leq u \lt v \leq N) を自由に選び、都市 u と都市 v を双方向に結ぶ道路を 1 本だけ新設することができます。そこで、以下で定められる値を スコア とします。

• 同じ道を 2 度通らずにある都市から同じ都市に戻ってくる経路における、通った道の本数 （この値はただ 1 つに定まる）

スコアとして考えられる最大の値を出力してください。

制約

• 3 \leq N \leq 100000
• 1 \leq A_i \lt B_i \leq N (1 \leq i \leq N-1)
• どの都市の間も、いくつかの道路を通って移動可能
• 与えられる入力は全て整数

入力例 1

3
1 2
2 3

出力例 1

3

都市 1 と 都市 3 の間に道路を建設します。そうすると、都市 1 → 都市 2 → 都市 3 → 都市 1 という経路で通る道の本数が 3 本となり、スコア 3 を達成できます。

入力例 2

5
1 2
2 3
3 4
3 5

出力例 2

4

都市 1 と 都市 5 の間に道路を建設します。そうすると、都市 1 → 都市 2 → 都市 3 → 都市 5 → 都市 1 という経路で通る道の本数が 4 本となり、スコア 4 を達成できます。

入力例 3

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

出力例 3

8

入力例 4

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

出力例 4

9