← 返回题目列表

AtCoder · arc022_3

C. 罗密欧与朱丽叶

中文机器翻译题面 查看原题

問題文

在高桥王国 有 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”也是正确的。