该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

巡游起点

题目描述

有 $N$ 座城市和 $N-1$ 条双向道路，保证这些道路构成一棵树。给定起点 $S$，按照下面的规则进行巡游：

1. 最初位于城市 $S$，将 $S$ 标记为已访问，并记录一次 $S$。
2. 设当前位于城市 $u$。如果 $u$ 存在尚未访问的相邻城市，就前往其中编号最小的一座城市，将它标记为已访问，并记录新到达的城市。
3. 如果 $u$ 不存在尚未访问的相邻城市，并且 $u\ne S$，就沿第一次到达 $u$ 时经过的道路返回上一座城市，并记录返回后所在的城市。
4. 如果当前位于 $S$，且 $S$ 不存在尚未访问的相邻城市，巡游结束。

请输出整个巡游过程中记录的城市序列。

输入格式

第一行给出整数 $N,S$（$2\le N\le 2\times 10^5$，$1\le S\le N$）。接下来 $N-1$ 行每行给出 $A_i,B_i$（$1\le A_i,B_i\le N$），保证这些边构成一棵树。

输出格式

按记录顺序输出 $2N-1$ 个城市编号，相邻编号之间用空格分隔。序列的第一个和最后一个编号都为 $S$。

输入输出样例 #1

输入 #1

4 2
1 2
4 2
3 1

输出 #1

2 1 3 1 2 4 2

说明/提示

从城市 2 出发，先前往编号更小的相邻城市 1。城市 1 继续前往城市 3；城市 3 没有未访问的相邻城市，因此依次返回城市 1 和城市 2。最后访问城市 4 并返回城市 2，记录序列为