题目描述

为了救出朋友，星期三来到了由古老诅咒创造的噩梦迷宫。迷宫由 $n$ 个房间和连接它们的 $n-1$ 条走廊组成，其结构是一棵树。每个房间都有一个互不相同的编号，编号从 $1$ 到 $n$。

施加在迷宫上的诅咒扭曲了空间，使星期三不仅能够从当前房间移动到相邻房间，还能直接移动到所有经过至多三条走廊就能到达的房间。换句话说，如果迷宫中两个房间之间的最短路径包含的走廊数不超过三，星期三就可以跳过中间的房间，在这两个房间之间直接移动。

为了解除诅咒并找到出口，星期三必须从任意房间出发，恰好访问每个房间一次，然后返回出发的房间。请输出一条这位阴郁的女主角可以采用的路线。

输入格式

第一行包含一个整数 $n$，表示噩梦迷宫的房间数，满足 $3\le n\le 2\cdot 10^5$。

接下来的 $n-1$ 行，每行包含两个整数 $u,v$，表示房间 $u$ 与房间 $v$ 之间有一条走廊，满足 $1\le u,v\le n$。

保证迷宫是一棵树。房间编号为 $1$ 到 $n$。

输出格式

输出 $n+1$ 个房间编号，表示星期三的路线。前 $n$ 个编号应恰好包含每个房间一次，最后一个编号与第一个编号相同。任意两个相邻编号所对应的房间之间，最短路径上的走廊数不得超过 $3$。

3
1 2
2 3

1 3 2 1

9
1 2
2 3
7 5
8 7
6 9
4 7
2 6
8 2

1 3 6 9 8 5 4 7 2 1