题目描述

给定一棵有 $n$ 个点的树。你需要构造一个数组 $a_1,a_2,\ldots,a_n$，满足：

• 每个 $a_i$ 都是 $1$ 到 $2n$ 之间的整数；
• $a_1,a_2,\ldots,a_n$ 两两不同；
• 对树上的每一条边 $(u,v)$，$|a_u-a_v|$ 都不是质数。

如果无法构造，输出 $-1$；否则输出任意一种合法数组。

输入格式

第一行一个整数 $t$，表示测试组数。

每组数据第一行一个整数 $n$，表示树的点数。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$，表示树上的一条边。

输出格式

对每组数据，如果存在合法数组，输出一行 $a_1,a_2,\ldots,a_n$；否则输出 $-1$。

样例

2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
2 4
3 5
3 6
3 7

2 10 1 6 5 
8 7 12 1 4 6 3

数据范围

$1\le t\le10^4$，$2\le n\le2\times10^5$，$1\le u_i,v_i\le n$，$u_i\ne v_i$。

保证给出的边构成一棵树，且所有测试组的 $n$ 之和不超过 $2\times10^5$。