存在各种类型的平衡树，例如高度平衡树和重量平衡树。也有为每个顶点分配颜色的树，例如红黑树。那么颜色平衡树呢？

如果一棵包含偶数个顶点的树满足以下性质，则称其为颜色平衡树：

• 每个顶点被分配一种颜色：青色或白色。
• 青色和白色顶点的数量相等。
• 对于树中的每一条简单路径，青色和白色顶点的数量之差的绝对值不得超过 3。

为了说明这些性质，你需要为给定树的每个顶点涂上青色或白色，使其成为一棵颜色平衡树（如果可能的话）。当然，树的顶点总数将是偶数，记为 $2n$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。每个测试用例：

• 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示共有 $2n$ 个顶点。
• 接下来有 $2n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le 2n$)，表示连接第 $u$ 个顶点和第 $v$ 个顶点的一条边。

保证给定的边构成一棵树，且所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例：

• 如果存在解，输出一行，包含 $2n$ 个整数 $c_1, c_2, \dots, c_{2n}$ ($c_i \in \{0, 1\}$)，并用空格分隔。如果 $c_i = 0$，则第 $i$ 个顶点涂为青色；否则，第 $i$ 个顶点涂为白色。
• 否则，输出一行 $-1$。

样例

样例输入 1

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

样例输出 1

0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0 1 0
1 1 1 0 0 0 1 0 1 0