問題文

正整数 $N$ が与えられます．ラベル付き $N$ 頂点単純連結無向木 $T$ と正整数 $M(1\leq M\leq N)$ に対して，以下の操作で得られる長さ $2N-1$ の数列を $f(T,M)$ とします：

• 頂点 $M$ から DFS をして辿った頂点を並べて得られる列．ただし，隣接頂点のうち訪れたことのないものをラベル順に訪問するとする．

$f$ の例

図のような木 $T$ の場合，

• $f(T,1)=(1,4,3,2,3,4,5,4,1)$
• $f(T,3)=(3,2,3,4,1,4,5,4,3)$

となります．

入力

$N$

• $1\leq N\leq 10^6$

出力

$g(1),g(2),\cdots,g(N)$ を $1$ 行に $1$ つずつ，合わせて $N$ 行出力してください． 最後に改行してください．

サンプル

3

11
10
11

4

127
119
119
127