木の直径を求める
頂点数 v の木が与えられており、あなたのタスクはこの木の直径を求めることです。直径とは、最も離れている2つの頂点間を結ぶパスの長さを指します。
入力
最初の行には単一の整数 v (1 ≤ v ≤ 100000) が与えられます。
続く v-1 行には、それぞれ整数 v1, v2 (1 ≤ v1, v2 ≤ v) がペアで与えられます。これは頂点 v1 と頂点 v2 が互いにつながっていることを意味します。
出力
与えられた木の直径を出力してください。
例
入力 | 出力 |
|---|---|
3 1 2 1 3 | 2 |
5 1 2 1 3 3 4 3 5 | 3 |
Hint 1
異なる頂点を始点として、複数回DFSを実行できます。
Hint 2
まずノード1を始点としてDFSを行い、最も遠い頂点を見つけてください（木にはサイクルがないため、BFSなしでも可能です）。
その後、見つけた頂点を始点にもう一度DFSを行い、さらに遠い頂点を探すことで、木の直径を求めることができます。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB