K - Problem on Tree Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

頂点数 N の木があります。木の頂点にはそれぞれ 1 から N までの番号が振られています。

辺は N-1 本あり、 i 番目の辺は頂点 p_i と頂点 q_i を結んでいます。

相異なる頂点の列 v_1, v_2, ..., v_M であって、次の条件を満たすもののうち、 M が最大となるものの M を求めてください。

  • 全ての 1 \leq i < M について、v_i と v_{i+1} を結ぶ経路の上に、v の他の頂点が存在しない。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq p_i, q_i \leq N
  • 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

N
p_1 q_1
p_2 q_2
:
p_{N-1} q_{N-1}

出力

条件を満たす相異なる頂点の列のうち要素数 M が最大となるものの M を出力せよ。

入力例 1

4
1 2
2 3
2 4

出力例 1

3

入力例 2

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

出力例 2

8

Score : 100 points

Problem Statement

There is a tree with N vertices, numbered 1 through N.

The i-th of the N-1 edges connects the vertices p_i and q_i.

Among the sequences of distinct vertices v_1, v_2, ..., v_M that satisfy the following condition, find the maximum value of M.

  • For every 1 \leq i < M, the path connecting the vertices v_i and v_{i+1} do not contain any vertex in v, except for v_i and v_{i+1}.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq p_i, q_i \leq N
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N
p_1 q_1
p_2 q_2
:
p_{N-1} q_{N-1}

Output

Print the maximum value of M, the number of elements, among the sequences of vertices that satisfy the condition.

Sample Input 1

4
1 2
2 3
2 4

Sample Output 1

3

Sample Input 2

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

Sample Output 2

8