题目描述

Jsp 很快解决了问题，Rlc 正要说什么，却见 Jsp 望向窗外。Rlc 心中一阵失落，顿时没了心情，低下头去默默流着眼泪。

不知过了多久， Rlc 被列车员的通报惊醒：「各位乘客，前方列车即将到达 Oli 国的首都 IlO 市。」Oli 国并不是 Jsp 和 Rlc 的目的地，不过这也让 Rlc 终于抓到了机会。

「Oli 国到了。」
「是啊 …… Oli 国 ……」
「据说曾经被评为地球上最和谐的国家之一呢，Jsp。」
「看起来和这个词没有任何关系？」
「是啊 …… 自从那次之后 ……」
「和你我又有什么关系呢？」
「也许吧。看着我，Jsp。」
「Rlc？」
「这三年你都做了什么呢？」
「OI。」
「接下来的两年呢？」
「……」

二人相对无言，直到列车到达终点。

OIi 国由 $n$ 个城市构成，从 $1$ 到 $n$ 编号，这 $n$ 个城市由 $n-1$ 条双向道路连通着。
其中每个城市的危险程度不同，城市按危险度从小到大排列为 $a_1,a_2,...,a_n$。
城市太过危险，所以每个城市需要有一个庇护所。定义每个城市的庇护所为与它相连（不包括自身）的危险度最小的城市，出于某种神秘的原因，任意两个不同的城市庇护所不同。

可惜，中央政府领导人 *****1317 忘了每个城市的危险度大小，也忘了每个城市庇护所的编号，只记得这些道路。
$a_1,a_2,...,a_n$ 可能有多种取值，但 *****1317 只关心其中字典序最小的。他想要让你给出字典序最小的合法的 $a_1,a_2,...,a_n$ 的取值。

输入格式

第一行一个正整数 $n$，表示城市的个数。
接下来 $n-1$ 行，每行两个正整数 $u,v$，表示有一条连接 $u,v$ 的双向道路（$1\leq u,v\leq n,u\neq v$）。

输出格式

如果合法的 $a_1,a_2,...,a_n$ 不存在，那么输出 -1。
否则输出字典序最小的合法的 $a_1,a_2,...,a_n$。

样例 1

input

4
3 1
1 2
4 2

output

3 2 4 1

容易验证，当城市按危险度从小到大排列为 $3,2,4,1$，即各个城市的危险程度从小到大的排名分别为 $4,2,1,3$ 时 1 号城市与 2 号，3 号城市相连，因此 1 号城市的庇护所为 3 号城市。 同样的 2 号城市的庇护所为 4 号城市， 3 号城市的庇护所为1号城市，4 号城市的庇护所为 2 号城市。这时候就满足任意两个不同城市的庇护所不同。

样例 2

input

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

output

2 1 3 5 6 9 7 10 4 8

数据范围与提示

对于所有数据，$1\leq n\leq 5\times 10^5$。