暂无测试数据。

百奇最近购买了一个新玩具 —— 树模型，百奇特别喜欢把这棵树摆来摆去玩。

每次百奇会确定这棵树的根，以及每个结点的儿子结点的顺序，并且记录下这棵树的先序遍历序列。

某一天，百奇发现他无论怎么摆弄树模型，它的先序遍历序列都已经被记录过了，因此百奇认为他记录下了所有可能的先序遍历序列。

现在百奇想知道这些序列中字典序最小的一个序列是什么（我们认为每个编号为一个字符）。

输入格式

输入文件的第一行输入一个正整数 $n$，表示树中的结点个数。

后接 $n-1$ 行，每行两个正整数 $u,v$，表示 $u$ 到 $v$ 在树中有一条边。

相邻两个数之间用一个空格隔开。

输出格式

输出文件只有一行，包含 $n$ 个整数，表示字典序最小的先序遍历序列。

数据范围

对于前 $20\%$ 的数据，保证每个结点度数不超过 $3$。

对于前 $50\%$ 的数据，$n \leq 2000$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5,\ 1 \leq u,v \leq n$。

4
1 2
1 3
2 4

1 2 4 3