Problem D
Factor-Full Tree

Aivar is very good at number theory. In fact, it is the only thing he is good at, but this doesn’t stop him from achieving great things. However, if Aivar wants to solve any problem in life, he first needs to convert it to number theory.

For example, consider a rooted tree with $N$ vertices. In order to deal with such structures, Aivar first constructs a divisor labelling of the tree. A divisor labelling is a way to label each vertex $v$ with a positive integer $x_ v$ so that $v$ is an ancestor of $u$ if and only if $x_ v$ divides $x_ u$.

After constructing such a labelling, Aivar can simply forget about the tree and just think about the list of numbers $x_1, x_2, \dots , x_ N$.

You are given a rooted tree with $N$ vertices, and your task is to find a divisor labelling. The vertices are numbered from $1$ to $N$, and $1$ is the root.

Input

The first line contains an integer $N$ ($1 \leq N \leq 60$).

The following $N-1$ lines each contain two integers $u$ and $v$ ($1 \leq u, v \leq N$, $u \neq v$), meaning that an edge goes between vertices $u$ and $v$. These edges will form a tree.

Output

Print one line with $N$ integers, the numbers $x_1, x_2, \dots x_ N$. These numbers must satisfy $1 \leq x_ i \leq 10^{18}$. It can be shown that under these constraints, an answer always exists.

5
1 2
1 3
3 4
3 5

1 2 3 21 33