F. Factor-Full Tree
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Example
Input
5
1 2
1 3
3 4
3 5
Output
1 2 3 21 33