약수가 가득한 트리

아이바르(Aivar)는 수론을 아주 잘한다. 사실 그가 잘하는 것은 이것 하나뿐이지만, 그렇다고 큰일을 이루지 못하는 것은 아니다. 다만 아이바르가 인생의 어떤 문제든 풀고 싶다면, 먼저 그 문제를 수론 문제로 바꿔야 한다.

예를 들어 $N$개의 정점을 가진 루트 트리를 생각해 보자. 이런 구조를 다루기 위해 아이바르는 먼저 트리의 약수 라벨링을 만든다. 정점 $v$가 $u$의 조상일 때에만 $x_v$가 $x_u$의 약수가 되도록, 각 정점 $v$에 양의 정수 $x_v$를 붙이는 것이 약수 라벨링이다.

약수 라벨링을 만든 뒤에는 아이바르가 트리를 잊어버려도 되고, 수열 $x_1, x_2, \dots, x_N$만 생각하면 된다.

$N$개의 정점을 가진 루트 트리가 주어진다. 약수 라벨링을 구하라. 정점은 1부터 $N$까지 번호가 매겨져 있고, 1번 정점이 루트이다.

첫 줄에 정수 $N$($1 \le N \le 60$)이 주어진다.

이후 $N-1$개의 줄에 각각 두 정수 $u$, $v$($1 \le u, v \le N$, $u \ne v$)가 주어진다. 이는 정점 $u$와 $v$ 사이에 간선이 있다는 뜻이다. 이 간선들은 트리를 이룬다.

한 줄에 정수 $x_1, x_2, \dots, x_N$을 공백으로 구분하여 출력한다. 이 수들은 $1 \le x_i \le 10^{18}$을 만족해야 한다. 이 조건에서 답이 항상 존재함이 증명되어 있다.