# Problem F

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.

Sample Input 1 | Sample Output 1 |
---|---|

5 1 2 1 3 3 4 3 5 |
1 2 3 21 33 |