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

关于题目正确性的声明

综合考虑，我们决定删除原本对于所谓“探索”和“战斗”过程的记载以及致谢内容，仅对题目本身给出一些客观公正的定论。

• 题目自身的难度较大，对标 cf rating 难度大致可以标注在 3300~3500 的范围。
• 解题的思考链和代码实现难度完全可以精简到一般算法竞赛意义下的可控范围，应当被视作一道常规的高难题目。
• 本题性能最优的解题方案为时间复杂度 $O(n\log n)$ 以及空间复杂度 $O(n)$，理论时间复杂度最优量纲为严格 $O(n)$。
• 官方评测数据在截止至 5.31 正式比赛之前不存在正确性问题，但官方解法的时间复杂度错误。即题目是以【未完成】的状态上架到正式比赛当中，最终官方数据在 7 月完成了补充。

时间限制： 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$，保证输入是一棵合法的树。

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