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