CF1131F Asya And Kittens

Asya 非常喜欢动物。最近，她买了 $n$ 只小猫，并给它们编号为 $1$ 到 $n$，然后把它们放进了一个笼子里。这个笼子由一排 $n$ 个单元格组成，从左到右编号为 $1$ 到 $n$。相邻的单元格之间有半透明的隔板，因此最初有 $n-1$ 个隔板。最开始，每个单元格里正好有一只编号的小猫。 在观察小猫们时，Asya 发现它们非常友好，经常有一对相邻单元格的小猫想要一起玩。因此，Asya 开始移除相邻单元格之间的隔板。具体来说，在第 $i$ 天，Asya 会： - 发现编号为 $x_i$ 和 $y_i$ 的小猫，位于相邻的单元格里，想要一起玩。 - 移除这两个单元格之间的隔板，将这两个单元格合并为一个单元格，里面包含原来两个单元格里的所有小猫。 由于 Asya 从未重新放回隔板，经过 $n-1$ 天后，笼子里只剩下一个单元格，里面有所有的小猫。 对于每一天，Asya 记得想要一起玩的小猫编号 $x_i$ 和 $y_i$，但她不记得最初是如何将小猫放进笼子的。请你帮她找出一种可能的小猫最初在 $n$ 个单元格中的排列方式。

第一行包含一个整数 $n$（$2 \le n \le 150\,000$），表示小猫的数量。 接下来的 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示在第 $i$ 天，由于移除隔板，编号为 $x_i$ 和 $y_i$ 的小猫合并到了同一个单元格。 保证在每一天，$x_i$ 和 $y_i$ 在这一天之前处于不同的单元格。

对于每个单元格 $1$ 到 $n$，输出一个整数，表示最初在该单元格里的小猫编号（$1$ 到 $n$）。所有输出的整数必须互不相同。 保证至少存在一种可行解。如果有多种答案，输出任意一种即可。

样例的答案是多种可能初始排列中的一种。 下图展示了对于该初始排列，每一天是如何合并单元格的。注意，每一天想要一起玩的小猫，确实在相邻的单元格中。  由 ChatGPT 4.1 翻译