Codeforces Round 992 (Div. 2) |
---|
Finished |
You are given a tree with n vertices.
You need to construct an array a1,a2,…,an of length n, consisting of unique integers from 1 to 2⋅n, and such that for each edge ui↔vi of the tree, the value |aui−avi| is not a prime number.
Find any array that satisfies these conditions, or report that there is no such array.
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains a single integer n (2≤n≤2⋅105) — the number of vertices in the tree.
The next n−1 lines contain the edges of the tree, one edge per line. The i-th line contains two integers ui and vi (1≤ui,vi≤n; ui≠vi), denoting the edge between the nodes ui and vi.
It's guaranteed that the given edges form a tree.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
For each test case, if an array that satisfies the conditions exists, print its elements a1,a2,…,an. Otherwise, print −1.
251 22 32 43 571 21 32 43 53 63 7
2 10 1 6 5 8 7 12 1 4 6 3
The possible answers are shown below. Instead of the vertex numbers, the corresponding elements of the array a are written in them.
Name |
---|