AT_arc022_3 [ARC022C] ロミオとジュリエット

[problemUrl]: https://atcoder.jp/contests/arc022/tasks/arc022_3 高橋王国には $ 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 $ を繋ぐ道があることを表す。

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

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 1,000 $ を満たすテストケースすべてに正解した場合は $ 40 $ 点が与えられる。 ### Sample Explanation 1 !\[\](/img/arc/022/3-1.png) この入力では、高橋王国は図のような構造をしている。 「10 5」と出力しても正解である。 ### Sample Explanation 2 !\[\](/img/arc/022/3-2.png) この入力では、高橋王国は図のような構造をしている。 「2 3」「3 2」「2 4」「4 2」「3 4」と出力しても正解である。