Aivar 非常擅长数论。事实上，这是他唯一擅长的领域，但这并不妨碍他成就伟大的事业。然而，如果 Aivar 想要解决生活中的任何问题，他首先需要将其转化为数论问题。

例如，考虑一棵有 $N$ 个顶点的有根树。为了处理这种结构，Aivar 首先构造树的“除数标号”（divisor labelling）。除数标号是指为每个顶点 $v$ 赋予一个正整数 $x_v$，使得 $v$ 是 $u$ 的祖先当且仅当 $x_v$ 整除 $x_u$。

在构造出这样的标号后，Aivar 就可以忽略树的结构，只考虑数字列表 $x_1, x_2, \dots, x_N$。

给定一棵有 $N$ 个顶点的有根树，你的任务是找到一个除数标号。顶点编号从 $1$ 到 $N$，且 $1$ 是根节点。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 60$)。

接下来的 $N - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le N, u \neq v$)，表示顶点 $u$ 和 $v$ 之间有一条边。这些边构成一棵树。

输出格式

输出一行，包含 $N$ 个整数，即数字 $x_1, x_2, \dots, x_N$。这些数字必须满足 $1 \le x_i \le 10^{18}$。可以证明，在这些约束条件下，答案总是存在的。

样例

样例输入 1

5
1 2
1 3
3 4
3 5

样例输出 1

1 2 3 21 33