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

高桥王国有 $N$ 个村庄，编号为 $1$ 到 $N$。有 $N-1$ 对村庄之间通过道路相连，保证任意两个村庄之间都可以通过若干条道路到达。 住在高桥王国的罗密欧先生和朱丽叶君要搬家。由于两人关系非常差，他们希望能搬到距离尽可能远的两个村庄。请你计算，两人分别应该搬到哪两个村庄，才能使他们所住村庄之间的距离最大。这里“村庄之间的距离”指的是，从一个村庄到另一个村庄需要经过的道路数。

输入通过标准输入给出。 > $N$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_{N-1}$ $B_{N-1}$ - 第 $1$ 行是一个整数 $N\ (2 \leq N \leq 10^5)$，表示高桥王国的村庄数。 - 接下来的 $N-1$ 行，每行包含两个用空格分隔的整数 $A_i\ (1 \leq A_i \leq N)$ 和 $B_i\ (1 \leq B_i \leq N)$，表示村庄 $A_i$ 和村庄 $B_i$ 之间有一条道路相连。

请输出一行，用空格分隔两个整数，分别表示罗密欧先生和朱丽叶君应该居住的村庄编号，使得他们之间的距离最大。输出末尾需换行。如果有多组答案，输出其中任意一组即可。

## 部分分 本题设有部分分。 - 若你能通过所有 $N \leq 1,000$ 的测试点，将获得 $40$ 分。 ## 样例解释 1  对于该输入，高桥王国的结构如图所示。输出“10 5”也是正确答案。 ## 样例解释 2  对于该输入，高桥王国的结构如图所示。输出“2 3”、“3 2”、“2 4”、“4 2”、“3 4”均为正确答案。 由 ChatGPT 4.1 翻译