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 $NN$ 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 $vv$ with a positive integer $x_{v}x\_v$ so that $vv$ is an ancestor of $uu$ if and only if $x_{v}x\_v$ divides $x_{u}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}x\_1,\; x\_2,\; \backslash dots,\; x\_N$.

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

입력

The first line contains an integer $NN$ ($1\le N\le 601\; \backslash leq\; N\; \backslash leq\; 60$).

The following $N-1N-1$ lines each contain two integers $uu$ and $vv$ ($1\le u,v\le N1\; \backslash leq\; u,\; v\; \backslash leq\; N$, $u\mathrm{\ne }vu\; \backslash neq\; v$), meaning that an edge goes between vertices $uu$ and $vv$. These edges will form a tree.

출력

Print one line with $NN$ integers, the numbers $x_1,x_2,\dots x_{N}x\_1,\; x\_2,\; \backslash dots\; x\_N$. These numbers must satisfy $1\le x_i\le {10}^{18}1\; \backslash leq\; x\_i\; \backslash leq\; 10^\{18\}$. It can be shown that under these constraints, an answer always exists.