C - ロミオとジュリエット Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋王国には N 個の村があり、1 から N の番号がついています。N-1 組の村の間は道で繋がっていて、どの村と村の間も道をいくつか辿ることによって移動できるようになっています。

高橋王国に住んでいるロミオさんとジュリエット君が引っ越しをすることになりました。2 人はとても仲が悪いので出来るだけ離れた村に引っ越したいと思っています。あなたは、2 人がそれぞれどの村に引っ越せば 2 人の住む村の間の距離が最大になるのかを計算してあげてください。ただし「村の間の距離」とは、片方の村からもう片方の村まで行くために通る必要のある道の本数であるとします。

入力

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

N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
  • 1 行目には、高橋王国にある村の個数を表す整数 N (2 ≦ N ≦ 10^5) が与えられる。
  • 2 行目から N-1 行では、村どうしをつなぐ道の情報が与えられる。このうち i 行目には、整数 A_i (1 ≦ A_i ≦ N) と B_i (1 ≦ B_i ≦ N) が空白区切りで書かれており、これは村 A_i と村 B_i を繋ぐ道があることを表す。

部分点

この問題には部分点が設定されている。

  • N ≦ 1,000 を満たすテストケースすべてに正解した場合は 40 点が与えられる。

出力

2 人の住む村の間の距離が最大にするときに、ロミオさんが住むべき村とジュリエット君が住むべき村の番号を表す整数を空白区切りで 1 行に出力せよ。出力の末尾に改行をいれること。答えが複数考えられる場合は、そのうちのいずれかを出力すれば良い。

入力例1

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

出力例1

5 10

この入力では、高橋王国は図のような構造をしている。 「10 5」と出力しても正解である。

入力例2

4
1 2
1 3
1 4

出力例2

4 3

この入力では、高橋王国は図のような構造をしている。 「2 3」「3 2」「2 4」「4 2」「3 4」と出力しても正解である。