题目来自第 42 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

关于子任务 4 正确性研判结果的声明

在截止至 5.31 命题结束时的官方做法在时间复杂度是错误的。

后续出题人从 7.7 开始对正确做法进行持续探索。经过了对出题人代码/民间 Hack 数据的数轮攻防迭代、对于修订题解的一轮推翻、在确定题目可做之后的数轮增量探索，最终明确了本题的子任务 4 存在时间复杂度 $O(n\log n)$ 和空间复杂度 $O(n)$ 的做法。详细的研判过程留档、个人解读、战斗过程经验分享、最终的态度声明可以见该链接。欢迎大家继续针对题解、hack 数据、bonus 版本可能存在的做法持续讨论交流。

因此原先关于子任务 4 正确性的指控也是错误的，相关指控内容我们将一字不改并公开留档，并明确标注出对应内容为事实性错误。至此子任务 4 的数据也正式恢复评测。

感谢出题人的全力战斗，也感谢大家对于此事的持续关注。正是因为大家不同程度的参与其中，才让我们共同见证了真相到来的时刻！

时间限制： 3.0 秒

空间限制： 1024 MB

题目描述

西西艾弗岛上某实验室设计了一套包含 $n$ 个字符的字符集，字符从 $1$ 到 $n$ 编号。本题中，我们无需关心这些字符具体是什么，只需用整数编号对其进行指代即可。

现有一棵 $n(n > 1)$ 个节点的简单树，每个节点有一个字符串。初始时，第 $i(1\le i\le n)$ 个节点的字符串只包含一个编号为 $i$ 的字符，也就是说 $n$ 个节点的所有字符构成了字符集 $\{1,2,\cdots,n\}$。

你可以对某一个节点进行一次「聚拢」操作：

• 将这个节点的字符串，和所有与它相邻节点的字符串一起进行重排（可以任意决定这些字符串的拼接顺序），重排后合并成一个字符串，作为这个节点的新字符串；所有与它相邻节点的字符串均被清空为空串。

你可以执行任意次操作，但是必须保证：

• 除了第一次操作，每次操作参与的字符串（在执行聚拢操作的节点或邻域节点上的字符串）中一定有一个字符串长度 $\ge 2$。

你需要最后将树上所有字符合并到一个字符串里，作为最终串。

求能够得到的字典序最小的最终串。

输入格式

从标准输入读入数据。

第一行包含一个正整数 $n$，表示树上的点数。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示树上的一条边。

输出格式

输出到标准输出。

输出一行 $n$ 个由空格分隔的整数，表示字典序最小的最终字符串。

7
3 5
5 7
3 1
2 5
3 4
6 4

1 2 3 5 7 4 6

样例 1 解释

样例对应的树结构为：

可通过以下 $3$ 次合法的「聚拢」操作得到字典序最小的最终串：

1. 对节点 $5$ 操作：合并 $2, 3, 5, 7$ 号点的字符，按升序拼接得 2 3 5 7。此时全树仅有这一个串长度 $\ge 2$。（其余参与点均清空，下同）
2. 对节点 $3$ 操作：合并 $1, 3, 4, 5$ 号点。拼接顺序为 $s_1 + s_5 + s_4$，得到 1 2 3 5 7 4。
3. 对节点 $4$ 操作：合并 $3, 4, 6$ 号点。拼接顺序为 $s_3 + s_6$，得到 1 2 3 5 7 4 6。

操作结束后，所有字符成功合并为一个字符串，即为答案。

子任务

对于所有测试数据，满足 $2\le n\le 10^5$，保证输入是一棵合法的树。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。