题目描述

你是大鱼，一天你在海里划水。

海可以看成一个坐标平面，海上有 $n$ 座小岛，第 $i$ 座小岛的坐标为 $\left( x_i, y_i \right)$，上面居住着 $i$ 个人。

你喜欢沿着平行于 $x$ 轴或 $y$ 轴的方向进行划水，你觉得一条划水的路线是快乐的，如果它满足如下条件：

1. 该路线平行于 $x$ 轴，从纵坐标负无穷远处划到正无穷远处；或该路线平行于 $y$ 轴，从横坐标负无穷远处到正无穷远处。
2. 沿着你划水的方向，至少经过一座小岛。
3. 你会求出沿途经过的所有小岛的人数的最大公约数，这个数最终为 $1$。 （ps: 特别地，定义一个数的最大公约数就是它本身）

你希望有尽可能多的快乐的划水路线，于是你找到了水神，希望她帮你控制这片海域来完成你的目标。

不幸的是，水神不能改变这些小岛的坐标，她只能调整每座小岛的人数，且需要保持 $n$ 座小岛的人数恰为 $1 \sim n$ 的一个排列。

不过水神的计算能力不怎么好，因此她需要你给出一组方案，然后她会按照你的方案来重新分配这 $n$ 座小岛的人数。

因此你的任务是：找出一组调整小岛人数的方案，使得在满足水神的条件下，快乐的划水路线数尽可能多。

输入格式

本题包含多组数据。

第一行包含一个正整数 $T$，表示数据组数。

对于每组数据，第一行包含一个正整数 $n$，表示小岛的个数。

接下来 $n$ 行，每行两个正整数 $x_i, y_i$，表示一座小岛的坐标。保证所有小岛的坐标两两不同。

输出格式

对于每组数据，输出两行：

1. 第一行输出一个整数，表示快乐的划水路线的数量的最大可能值。
2. 第二行输出 $n$ 个整数，表示每座小岛的人数，按照输入的顺序输出。你需要保证你输出的 $n$ 个数恰为 $1 \sim n$ 的排列。

如果有多组解，输出任意一组均可。

注意：如果你对于所有的数据，第一行的输出均正确，可以获得该子任务 $25\%$ 的分数。但是如果你只要这个部分分，你也要在第二行输出一个排列 (但不需要满足你的答案)。

样例 1

输入

2
4
1 1
1 2
2 1
2 2
5
1 1
2 2
4 4
8 8
16 16

输出

4
1 2 4 3
2
1 2 3 4 5

样例 1 解释

• 对于第一组数据： 快乐的划水路线有四条：$x = 1$（沿途经过的小岛人数分别为 $1, 2$）、$x = 2$（人数分别为 $4, 3$）、$y = 1$（人数分别为 $1, 4$）、$y = 2$（人数分别为 $2, 3$）。
• 对于第二组数据： 快乐的划水路线有两条：$x = 1$（人数分别为 $1$）、$y = 1$（人数分别为 $1$）。

数据范围与提示

对于所有的测试点，均满足 $1 \leq T, n \leq 2 \times 10^5$；$\sum n \leq 2 \times 10^5$；$1 \leq x_i, y_i \leq 10^9$，对于 $i \neq j$，保证 $x_i \neq x_j \lor y_i \neq y_j$。

具体的子任务的数据规模见下表：

子任务	分值	$n$	$T$	$x_i,y_i$	其他性质
1	4	$\leq 9$	$\leq 6$	$\leq n$	无
2		$\leq 2 \times 10^5$		$\leq 10^9$	$x_i = y_i$
3					$y_i = 1$
4					$y_i \leq 2$
5	8	$\leq 9$	$\leq n$		无
6		$\leq 50$			$\sum n \leq 2500$
7		$\leq 2500$			无
8		$\leq 2 \times 10^5$	$= 1$		保证所有小岛构成一个 $4$-连通块
9	4		$\leq 2 \times 10^5$		无
10	8		$= 1$		保证每条平行于坐标轴的直线经过的小岛个数不等于 $2$
11	4		$\leq 2 \times 10^5$		无
12	8		$= 1$		保证每条平行于坐标轴的直线经过的小岛个数等于 $0$ 或 $2$
13	4		$\leq 2 \times 10^5$		无
14	8		$= 1$	$\leq 10000$	保证所有小岛的坐标在可行域内均匀随机
15	4		$\leq 2 \times 10^5$		无
16	8		$= 1$	$\leq 10^9$
17	4		$\leq 2 \times 10^5$

注：两个整点 $A, B$ 是 $4$-连通的，当且仅当存在一个整点序列 $P_0 = A, P_1, P_2, \cdots, P_{m-1}, P_m = B$，使得 $\left| P_i P_{i+1} \right| = 1$（$0 \leq i < m$）。

注意：如果你对于所有的数据，第一行的输出均正确，可以获得该子任务 $25\%$ 的分数。但是如果你只要这个部分分，你也要在第二行输出一个排列 (但不需要满足你的答案)。（很重要所以说两遍）

---