あなたは「大魚」であり、ある日海で泳いでいます。
海は座標平面とみなすことができ、海の上には $n$ 個の小島があります。第 $i$ 番目の小島の座標は $\left( x_i, y_i \right)$ であり、そこには $i$ 人が住んでいます。
あなたは $x$ 軸または $y$ 軸に平行な方向に泳ぐのが好きです。ある泳ぐルートが「楽しい」とは、以下の条件を満たすことを指します。
- そのルートは $x$ 軸に平行で、縦座標の負の無限遠から正の無限遠まで泳ぐか、あるいは $y$ 軸に平行で、横座標の負の無限遠から正の無限遠まで泳ぐものである。
- 泳ぐ方向に沿って、少なくとも 1 つの小島を通過する。
- 途中で通過したすべての小島に住む人数の最大公約数を求めると、その値が $1$ になる。
(ps: 特に、1つの数の最大公約数はその数自身と定義する)
あなたはできるだけ多くの「楽しい」泳ぐルートを望んでいるため、水の神に頼んでこの海域を制御してもらい、目標を達成しようと考えました。
あいにく、水の神は小島の座標を変更することはできません。彼女ができるのは各小島に住む人数を調整することだけであり、その際、$n$ 個の小島に住む人数が $1 \sim n$ の順列になるように保つ必要があります。
しかし、水の神は計算があまり得意ではないため、あなたが計画を提示し、彼女がその計画に従って $n$ 個の小島の人数を再割り当てすることになりました。
したがって、あなたのタスクは、水の神の条件を満たした上で、「楽しい」泳ぐルートの数が最大となるような、小島の人数を調整する計画を提示することです。
入力
この問題は複数のテストケースを含みます。
1行目に正整数 $T$ が与えられ、データセットの数を示します。
各データセットについて、1行目に正整数 $n$ が与えられ、小島の数を示します。
続く $n$ 行には、各行に2つの正整数 $x_i, y_i$ が与えられ、小島の座標を示します。すべての小島の座標は互いに異なることが保証されています。
出力
各データセットについて、2行を出力してください。
1行目に、「楽しい」泳ぐルートの数の最大可能値を出力してください。
2行目に、$n$ 個の整数を出力してください。これは各小島に住む人数を表し、入力された順序で出力します。出力する $n$ 個の数が $1 \sim n$ の順列であることを保証してください。
複数の解が存在する場合、どれを出力しても構いません。
注意：すべてのデータに対して1行目の出力が正しければ、そのサブタスクの $\color{red}{25 \%}$ のスコアを獲得できます。ただし、この部分点のみを狙う場合でも、2行目には必ず順列を出力する必要があります（ただし、その順列が1行目の答えを満たしている必要はありません）。
入出力例
入力 1
2 4 1 1 1 2 2 1 2 2 5 1 1 2 2 4 4 8 8 16 16
出力 1
4 1 2 4 3 2 1 2 3 4 5
注記 1
1つ目のデータセットについて：
「楽しい」泳ぐルートは4つあります：$x = 1$ (通過する小島の人数は $1, 2$)、$x = 2$ (人数は $4, 3$)、$y = 1$ (人数は $1, 4$)、$y = 2$ (人数は $2, 3$)。
2つ目のデータセットについて：
「楽しい」泳ぐルートは2つあります：$x = 1$ (人数は $1$)、$y = 1$ (人数は $1$)。
入力 2
配布ファイルを参照してください。
小課題
すべてのテストケースにおいて、$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 \vee y_i \neq y_j$ が保証されます。
各サブタスクのデータ規模は以下の表の通りです：
| サブタスク | 配点 | $n$ | $T$ | $x_i, y_i$ | その他性質 |
|---|---|---|---|---|---|
| $1$ | $4$ | $\le 9$ | $\le 6$ | $\le n$ | なし |
| $2$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $x_i = y_i$ |
| $3$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $y_i = 1$ |
| $4$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $y_i \le 2$ |
| $5$ | $8$ | $\le 9$ | $\le 2\times 10^5$ | $\le n$ | なし |
| $6$ | $8$ | $\le 50$ | $\le 50$ | $\le 10^9$ | $\sum n \le 2500$ |
| $7$ | $8$ | $\le 2500$ | $\le 2500$ | $\le 10^9$ | $\sum n \le 2500$ |
| $8$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | すべての小島が1つの $4-$連結成分を構成する |
| $9$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | すべての小島が1つの $4-$連結成分を構成する |
| $10$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | 座標軸に平行な各直線が通過する小島の数が $2$ ではないことを保証する |
| $11$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | 座標軸に平行な各直線が通過する小島の数が $2$ ではないことを保証する |
| $12$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | 座標軸に平行な各直線が通過する小島の数が $0$ または $2$ であることを保証する |
| $13$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | 座標軸に平行な各直線が通過する小島の数が $0$ または $2$ であることを保証する |
| $14$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10000$ | すべての小島の座標が可視領域内で一様ランダムであることを保証する |
| $15$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10000$ | すべての小島の座標が可視領域内で一様ランダムであることを保証する |
| $16$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | なし |
| $17$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | なし |
注：2つの格子点 $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$) を満たすことを指す。
注意：すべてのデータに対して1行目の出力が正しければ、そのサブタスクの $\color{red}{25 \%}$ のスコアを獲得できます。ただし、この部分点のみを狙う場合でも、2行目には必ず順列を出力する必要があります。（重要なので二度言います）
また、選手の心身の健康のため、配布ファイル内に checker.cpp を用意しました。各自コンパイルして使用してください。使用方法およびヘッダーファイルについては testlib の標準に従ってください。