30437번 - 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.

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.

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.