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