Factor-Full Tree

Aivar is very good at number theory. In fact, it is the only thing he is good at, but this does not 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. To work with such structures, Aivar first constructs a divisor labelling of the tree. A divisor labelling assigns each vertex $v$ 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 forget about the tree and consider only the list of numbers $x_1, x_2, \dots, x_N$.

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

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

Each of the following $N-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le N$, $u \ne v$), meaning that an edge connects vertices $u$ and $v$. These edges form a tree.

Print one line with $N$ integers $x_1, x_2, \dots, x_N$. These numbers must satisfy $1 \le x_i \le 10^{18}$. It has been shown that under these constraints, an answer always exists.