Description

给一棵树，要求用一个序列 $p_1,p_2,\ldots, p_{n-1}$ 表示这棵树，其中 $p_i$ 表示 $i$ 与 $p_i$ 有一条边。

Input

第一行一个整数 $n\ (2\le n\le 10^5)$。

接下来 $n-1$ 行，每行两个整数 $u,v\ (1\le u,v\le n,u\neq v)$，表示树上的一条边。保证输入描述了一棵合法的树。

Output

输出一行 $n-1$ 个整数 $p_1,p_2,\ldots, p_{n-1}$，其中 $p_i$ 表示 $i$ 与 $p_i$ 有一条边。

Samples

5
1 2
1 3
2 4
2 5

2 5 1 2

Resources

The 21st UESTC Programming Contest Preliminary