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 翻译