说明

在 Trilyandia 国家，有 $n$ 个城市通过 $n-1$ 条道路相连。该国的道路系统很特别：

• 每条道路仅连接两个不同的城市；
• 任意两个城市之间最多有一条道路；
• 从任意城市出发，都可以到达其他任意城市（可能需途经其他城市）。

邮政公司 OldPost 决定在该国提供配送服务。由于员工人数有限，运输仅沿一条长度为 $l$ 的路线 $a$ 进行，即一个城市序列 $a_1,a_2,\dots,a_l$，满足：

• 对于 $i\neq j$，有 $a_i\neq a_j$；
• 城市 $a_i$ 和 $a_{i+1}$ 之间有道路连接（$1\leq i < l$）。

为了最大化利润，OldPost 决定沿长度最长的路线运营。

OldPost 的古老竞争对手 NewPost 也决定做同样的事，但沿其自己的路线 $b$：$b_1,b_2,\dots,b_l$，该路线不一定与 $a$ 不同，但也具有最大可能长度。

总统得知两家公司的意图后，要求 OldPost 和 NewPost 选择路线 $a$ 和 $b$，使得覆盖的城市数量最多（即确保尽可能多的城市至少出现在一条路线上）。由于 Trilyandia 的总统擅长管理，而邮政公司擅长投递物品而非寻找路线，因此你需要找出这样的 $a$ 和 $b$。

注意，每家公司都希望自己的路线长度尽可能长；即使选择更短的路线能增加覆盖的城市总数。

请帮助找出具有最大可能长度且覆盖最多城市数量的路线 $a$ 和 $b$。

输入格式

• 第一行包含一个整数 $n$（$2\leq n \leq 6\cdot 10^5$）——国家中的城市数量。
• 接下来的 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i,y_i \leq n, x_i \neq y_i$）——表示有道路连接的城市对。

输出格式

• 第一行应包含一个整数 $l$（$2 \leq l \leq n$）——找到的贸易路线的长度。
• 第二行应包含 $l$ 个整数 $a_1,a_2,\dots,a_l$（$1 \leq a_i \leq n$）——路线 $a$ 中的城市。
• 第三行应包含 $l$ 个整数 $b_1,b_2,\dots,b_l$（$1 \leq b_i \leq n$）——路线 $b$ 中的城市。

如果有多个最优路线，输出任意一组即可。

10
1 2
2 3
3 4
4 5
2 6
6 7
3 8
8 9
10 1

6
5 4 3 2 1 10 
9 8 3 2 6 7 

提示

:::align{center} :::

在示例中，可能的最长路线如下：

• $5$-$4$-$3$-$2$-$6$-$7$
• $9$-$8$-$3$-$2$-$6$-$7$
• $5$-$4$-$3$-$2$-$1$-$10$
• $9$-$8$-$3$-$2$-$1$-$10$

第一条和第四条路线可以覆盖所有城市。

评分细则

• （$8$ 分）：$n\leq 10$；
• （$8$ 分）：$n\leq 20$；
• （$6$ 分）：$n \leq 1\,000$；恰好有一个城市直接与其他所有城市相连；
• （$8$ 分）：$n \leq 20\,000$；恰好有两个城市只与另一个城市相连（城市呈链状）；
• （$8$ 分）：$n \leq 20\,000$；恰好有一个城市与三个或更多城市相连；
• （$8$ 分）：$n \leq 10\,000$；最多有 $10$ 个城市只与另一个城市相连；
• （$16$ 分）：$n\leq 1\,000$；
• （$18$ 分）：$n\leq 70\,000$；
• （$20$ 分）：无额外限制。

翻译由 DeepSeek V3 完成