题目描述

Aivar 非常擅长数论。事实上，这几乎是他唯一擅长的事，但这并不妨碍他完成伟大的事情。不过，如果 Aivar 想解决生活中的任何问题，他首先都要把它转化成数论问题。

例如，考虑一棵有 $N$ 个点的有根树。为了处理这种结构，Aivar 首先会构造这棵树的一个整除标号。整除标号是指给每个点 $v$ 标上一个正整数 $x_v$，满足：

$$v \text{ 是 } u \text{ 的祖先} \quad\Longleftrightarrow\quad x_v \mid x_u .$$

构造出这样的标号后，Aivar 就可以忘掉原来的树，只思考数字列表 $x_1,x_2,\dots,x_N$。

给定一棵有 $N$ 个点的有根树，请找出一种整除标号。点编号为 $1$ 到 $N$，其中 $1$ 是根。

输入格式

第一行包含整数 $N$。

接下来 $N-1$ 行，每行包含两个整数 $u,v$，表示点 $u$ 与点 $v$ 之间有一条边。输入保证这些边构成一棵树。

$$1\le N\le 60,\qquad 1\le u,v\le N,\qquad u\ne v$$

输出格式

输出一行 $N$ 个整数 $x_1,x_2,\dots,x_N$。这些整数必须满足：

$$1\le x_i\le 10^{18}.$$

可以证明，在上述限制下答案一定存在。

输入输出样例 #1

输入 #1

5
1 2
1 3
3 4
3 5

输出 #1

1 2 3 21 33