Prime Tree - 4

A tree is a connected undirected graph that has no cycles. Consider a tree with n vertices, labeled with the integers 1, 2, ..., n. Call an edge (u, v) bad if there is an integer d > 1 such that the label of u and the label of v are both divisible by d. For example, the tree below has three bad edges: 6 and 4 are both divisible by 2, 2 and 6 are both divisible by 2, and 3 and 6 are both divisible by 3.

Your goal is to relabel the vertices so that the number of bad edges is as small as possible. For example, if you relabel the vertices of the tree above as shown below, only one bad edge (3, 6) remains.

The fewer bad edges your tree has, the more points you get.

This is an output-only problem. Run your program locally and submit only the answer file for each input file.

Each input file contains several test cases.

The first line of the input file contains the number of test cases in this input file.

The first line of a test case contains a single integer n, the number of vertices in the tree.

Each of the following n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n), the vertices connected by an edge.

All trees in a single file have the same number of vertices.

For each test case, print one line containing exactly n distinct integers from 1 to n: the labels assigned to vertices 1, 2, ..., n.

The first test case is shown in the problem statement above. After relabeling there is one bad edge (6, 3), because both 6 and 3 are divisible by 3.

In the second test case the edges are (5, 1), (5, 2), (5, 3), (5, 4), and (5, 6). None of them are bad.

The input file has 10 edges and the answer has 1 bad edge. So M = 10, X = 1, R = 0.1. According to the scoring table, this answer would get 5 points.

The tests have the following structure.

• Input file 1 contains three trees on 7 vertices, shown below from left to right.

• Input files 2 and 3 contain 100 random trees on 10 and 30 vertices respectively.
• Input files 4 to 8 contain various randomly generated trees with some special structure (for example, trees with many leaves, binary trees). The distribution of the different kinds of trees is roughly the same across all inputs.
• Input files 9 and 10 contain randomly generated trees of 50 000 and 100 000 vertices respectively.

Initially, the vertex labels of all trees in all input files are random.

Grading uses data-4.in from the archive.