题目描述

给定一棵树，可以从任意点出发，通过树上的边访问所有点， 每一条边至多经过两次 。每访问一个之前没有访问过的点，就会记下这个点的编号，必须保证每个点至少访问一次，当访问完成后，会发现自己记录的 $n$ 个点按记录的先后顺序排成了一排，这被称为一个 WKTM 序列，我们可以将这个 WKTM 序列当成一个 $n+1$ 进制的 $n$ 位数字，如：当 $n = 5$ 时，序列 $1, 2, 3, 4, 5$ 可看作 $1 \cdot 6^4 + 2 \cdot 6^3 + 3 \cdot 6^2 + 4 \cdot 6+5$ 。现在你需要计算可能的所代表数字最小的 WKTM 序列是什么。

输入格式

第一行一个正整数 $n$ 表示树的点数。

接下来 $n - 1$ 行，每行两个正整数 $x_i,\ y_i$ ，表示编号为 $x_i,\ y_i$ 的节点之间有一条边。

输入保证 $x_i,\ y_i \in [1,\ n]​$ ，且保证这些边能构成一棵树。

输出格式

输出一行 $n$ 个整数，相邻整数用空格隔开，表示代表数字最小的 WKTM 序列。

样例

样例输入

4
1 2
1 3
1 4

样例输出

1 2 3 4

数据范围与提示

$1 \le n \le 10^5$