Bonus Ver. 为本题原本的形态，后续因为各种原因进行削减，从而未在正式场上出现。我们提供一个额外的评测链接用于展示我们的探索成果。更多说明请参考本题的【附录】一章。

虽然我们欢迎大家的持续讨论和探索，但是参考本题【附录】一章，在探索时务必慎之又慎，讨论时也要为自己的探索结果与学术声誉负责，不要白白浪费大家的时间精力。滥用本题评测将会被封号处理。

时间限制： 3.0 秒

空间限制： 1024 MB

题目描述

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

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

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

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

你可以执行任意次操作。

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

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

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

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

1 2 3 4 5 6 7

样例 1 解释

样例对应的树结构为：

记 $s_u$ 为节点 $u$ 当前的字符串。可以通过以下 $3$ 次「无限制聚拢」操作得到最优答案：

1. 对节点 $2$ 操作：按照 $s_1+s_2$ 的顺序拼接，得到 1 2，放在节点 $2$；节点 $1$ 被清空。
2. 对节点 $6$ 操作：此时节点 $1$ 为空，其余参与的非空字符串位于节点 $3,4,5,6,7$。按照 $s_3+s_4+s_5+s_6+s_7$ 的顺序拼接，得到 3 4 5 6 7，放在节点 $6$；节点 $3,4,5,7$ 被清空。节点 $2$ 上的 1 2 保持不变，此时树上有两个独立的，长度至少为 $2$ 的字符串。
3. 对节点 $1$ 操作：节点 $1$ 虽然为空，但可以作为聚拢中心。按照 $s_2+s_6$ 的顺序拼接，得到 1 2 3 4 5 6 7，放在节点 $1$；节点 $2,6$ 被清空。

最终串已经是所有字符的升序排列，因此字典序最小。

作为对比，若对聚拢操作添加“除了第一次操作，每次聚拢都必须有一个长度至少为 $2$ 的字符串参与”这个限制。则同一棵树的最优答案为 1 2 6 3 4 5 7，可以从初态通过以下 $2$ 次「有限制聚拢」操作得到：

1. 对节点 $1$ 操作：按照 $s_1+s_2+s_6$ 的顺序拼接，得到 1 2 6，放在节点 $1$；节点 $2,6$ 被清空。
2. 对节点 $6$ 操作：按照 $s_1+s_3+s_4+s_5+s_7$ 的顺序拼接，得到 1 2 6 3 4 5 7，放在节点 $6$；其余非空节点被清空。这一步有节点 $1$ 上长度为 $3$ 的字符串参与，满足原问题的限制。

本题的三步方案中，第二步只聚拢若干单字符，不受上述限制，因此能够先独立形成第二个长度至少为 $2$ 的字符串，并得到更小的最终答案。

子任务

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

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

子任务编号	分值	$n\le$
1	20	$5$
2		$7$
3		$9$
4		$11$
5		$13$

提示

请注意「无限制聚拢」和「有限制聚拢」的区别。

附录 1

“真正可怜的，并不是无法报仇，而是被复仇束缚，连自己的人生都无法去活。”——芳村功善《东京喰种》

“即使不断累积憎恨、最终登上顶点，那里也不存在真正的胜利。在那之后存在的，只是永无止境的憎恨连锁！”——亚图姆《游戏王 DM》

“我不能与你同去。蓝神君，憎恨的尽头是一片虚无。”——武藤游戏《游戏王 次元之暗面》

“唯有不忘记过去、不否定过去，并接受它，才能让已经失去的东西继续拥有意义。”——卫宫士郎《Fate/stay night》

附录 2

目前能够探索到解决本问题的复杂度上界量纲无一例外均为 $O(2^{O(n\log n)})$（仅支路长度为 1 或 2 的星形树存在 $O(n^6)$ 的算法），也就是说，现在本题依旧是“不可做”状态（针对更大子任务的 $n$ 而言）。但是在 P 与 NP 相关的证明当中，只能证明是 NP 的，既不能证明为 NP-Hard（从而得到是 NP 完全的），也找不到可以规约的 P 算法。本着对理论计算机科学的敬畏，我们目前依旧将本问题标注为 Open Problem。

即便现阶段大模型已经非常强悍，但也不是什么问题都能靠大力抽卡就解决的。一方面，我们欢迎理论计算机科学爱好者或专业人士给出证明的后续探索方向；另一方面，我们也会等待大模型的后续发展，在成熟的时机下继续探索答案。毕竟 N-S 方程都被突破了，P 与 NP 问题还会远吗（笑）？

上界相同的不同做法在具体的表达式上仍有区别。综合考虑，初步将上界定为 $n\le 13$。我们在进行算法攻防时，对于 Hack 数据是随缘添加的（即让错误做法无法得到满分即可），因此在未得到满分却完整通过其中一个子任务时，并不代表在该子任务下全部正确。

虽说我们欢迎大家的讨论，或者持续为探索解决本问题做出贡献。但是我们现阶段没探索出明确的结果，并不代表我们没有穷尽现在可以使用的全部手段。经过之前的事件，我已经真的很疲惫了，不想再对着那些看上去唬人或者看上去合理但是有结构性错误的可以量产的垃圾去找反例了。因此这一次我们进行了充分的算法攻防测试，得到了 40 多组复杂度形如 $O(c^n\cdot \text{poly}(n))$ 的算法策略并分别给出了对应的 Hack 数据，其中有一些做法正经花费了一些时间才找到 Hack（具体可以参考附件区的现有攻防报告和研究报告）。

所以，如果真的想持续推进解决本问题，我们只有在满足以下条件才会推进探索：

• 如果能够真的找到 P 算法，请不要立刻提交代码，而是先给出结构化的规约证明、lean 的形式化证明。如果是错误做法，可以先自己构造并提供 hack，不要单方面指望我们持续出 hack 数据，真挺浪费时间精力的（而且还浪费 token）。
• 如果能够证明为 NP-Hard（又或者证明一定不属于 P 或者不属于 NP-Hard），也请给出结构化的规约证明以及 lean 的形式化证明。
• 严谨来说，即便完成上述内容，也需要等待“P=NP”被证明或者证伪才能下结论；但是这个可以先不去考虑。

当然，以防再有某些人阴阳我是无脑信 GPT 的小鬼，这里我要明确说明：AI 和形式化证明现在依旧会犯错。

这里我们举两个例子：

• 如何评价T.S. Arthanari宣称证明P=NP问题且通过lean 4验证？ “写数学论文一定要懂数学，跑 lean 一定要懂 lean”，别搞出循环论证或则上来就定义一个公理这种闹剧。
• 我被AI坑惨了：60页论文全部白写，AI为什么检查不出自己的错误？ - 钰子一 现阶段 AI 依旧还是会有检查不出来的错误（虽说 GPT 6-Pro 以及 6-Astra 实测下来出现幻觉的概率相对来说已经低不少了）。up 主的其中一句话说得很好：“幸好没有挂到 arxiv 上面，要不然的话，学术声誉可能就会下降很多的。”希望大家能记住，人类最后依旧要对 AI 给出的结果负责任。

还是希望大家对自己的学术声誉负责，不要白白浪费别人的时间。也希望大家对于出题也好、学术研究与交流也好、客观事实也好，都能有一分敬畏。

附录 3

从 GPT-5.5 到 GPT-5.6 再到 GPT-6，其在数学/理论计算机科学上都出现了相当大的突破，即便之前的闹剧不再有所谓“探索新范式”的性质，但是我的内心依旧在期待未来人机协作的新范式是什么样的（这里也并不局限于教育或者竞技类编程这些领域）。

当然，现在 AI 进化到这个程度，现在大家都在拿 GPT 对着过往的一些难题尝试探索更优做法（至少洛谷和 QOJ 都在这么干，我们后续在有时间精力的情况下也会去做这件事）。至少这和我之前的一些想象已经有了天差地别，我现在也很难想象新秩序下的研究范式到底会是什么样子，感觉就跟下面的“合订本”差不多吧。

这是最坏的时代，也是最好的时代。研究与教育的新范式究竟会前往何处，还需要大家一起来探索。

当然，无论未来我们会迈向何方，希望大家都能拥抱变化，时刻保持对真相的敬畏与好奇心，尽情享受这个黄金时代吧！Enjoy it~