有一棵 $N$ 个顶点的树。小泽从顶点 $1$ 出发，重复下面的行动：

• 若当前位置存在尚未访问过的相邻顶点，就走向其中编号最小的一个；
• 否则，若当前位置不是顶点 $1$，就沿来路返回父节点；
• 回到顶点 $1$ 且所有顶点都访问过时结束。

顶点在到达时都要记录，包括回退时再次到达的顶点。请输出完整记录序列。

输入格式

第一行输入 $N$。

接下来 $N-1$ 行输入树边。

输出格式

按到达顺序输出顶点编号。

4
1 2
3 4
1 3

1 2 1 3 4 3 1

5
4 5
1 2
1 4
2 3

1 2 3 2 1 4 5 4 1

6
1 5
1 2
1 3
3 4
1 6

1 2 1 3 4 3 1 5 1 6 1

数据范围与约定

• $2 \le N \le 2\times10^5$