问题描述

高桥王国有 $N$ 个村庄，编号从 $1$ 到 $N$。$N-1$ 对村庄之间相互连接，任意两个村庄之间可以通过道路进行移动。

罗密欧和朱丽叶住在高桥王国，他们决定搬家。由于他们关系很糟糕，他们希望尽可能住在相距较远的村庄。请计算出他们应该搬到哪个村庄，以使他们之间的距离最大化。这里的「村庄之间的距离」指的是从一个村庄到另一个村庄所需经过的道路数量。

输入

输入数据从标准输入读取，具体格式如下：

$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$ 分。

输出

输出两个整数，表示为罗密欧和朱丽叶应该居住的村庄编号，以空格分隔，放在一行上并以换行符结束。如果有多个答案，只需输出其中之一即可。

示例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」也是正确的答案。