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

关于子任务 4 正确性研判过程的声明

经过研判，官方给出的子任务 4 解法是错误的，其提供的解法时间复杂度依旧可以被边界数据卡到 $O(n^2\log n)$。目前也无法找出其他时间复杂度为 $O(n\log n)$ 的做法。

因此我们暂时只提供前 3 个子任务的评测，本评测链接目前满分为 60 分。如果探索到其他复杂度可能为 $O(n\log n)$ 的做法，欢迎通过联系方式与我们共同交流探讨。

更新 1：具体参考出题人的进一步回复和讲解，我们暂时恢复了子任务 4 的评测。这几天内我们会尽快完成对更新版本 std 的研判，也可能会因此带来数据更新和反复的重测，相关的研判与沟通过程也会在知乎进行留档。无论最终的结果如何，都将会对大家公开透明，并接受所有人的评判。

更新 2：目前得到了一些足够乐观的消息，应该可以初步认定作者的最新 std 是正确的了。目前最后的工作还差最后的单元压力测试、证明闭环、全部情况的详细说明。

更新 3：了转反，又出现新的 hack 数据了，还是需要再持续迭代一下。 经过研判，已经确定出题人于 7.7 提供的题解版本可以被推翻，具体内容请等待我方在知乎回答内容的更新。请大家稍安勿躁，我们会尽快完成相关内容的撰写。

更新 4：局势进一步逆转，我们将立刻进行下一轮的研判。 目前在压力测试环节已经找到了时间复杂度 Hack 数据，但是为了稳妥起见，sub 4 所有数据的答案将由多线程版本的 60 分代码生成，顺带可以进行正确性的判断。因此数据上新和重测还需要再等一会儿，请耐心等待。 目前出题人的更新修复了本问题，继续推进研判。

更新 5：我们正在对目前最终的代码进行证明闭环过程，中间进行了较多的单元测试和证明过程修订。请耐心等待我们最终的更新。

为了稳妥起见，sub 4 所有数据的答案将由多线程版本的 60 分代码生成，顺带可以进行正确性的判断。因此后续的数据上新和重测都会需要一定的时间，请耐心等待。

时间限制： 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。

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

子任务

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

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