Minimizing Bad Edges in a Tree

Given a tree with \(n\) nodes numbered from \(1\) to \(n\), an edge \((u,v)\) is called a bad edge if there exists an integer \(d > 1\) such that \(d \mid u\) and \(d \mid v\). For example, in a sample tree, the edges \((6, 4)\), \((2, 6)\), and \((3, 6)\) are bad edges since \(2\) divides both \(6\) and \(4)\), and similarly for the others.

Your task is to reassign the node labels (i.e. produce a permutation of \(\{1,2,\ldots,n\}\)) to minimize the number of bad edges in the tree. The fewer the number of bad edges after renumbering, the higher your score.

This is a submit-answer problem. You should download the output file, run your program locally to generate an output, and then upload the result. Of course, you can also submit your solution directly to the online judge.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of nodes in the tree. The following \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le n\)), indicating there is an edge between nodes \(u\) and \(v\). It is guaranteed that the given edges form a tree.

outputFormat

Output a permutation of \(\{1,2,\ldots,n\}\) representing the new assignment of node labels. The output should consist of \(n\) integers separated by spaces. Any valid permutation is acceptable.

sample

3
1 2
1 3

1 2 3