Description

鹿乃子乃子有著在睡覺時翻個身就能滾到學校的能力

鹿乃子乃子有著神奇的睡相，讓她在睡醒後可能會掛在電線桿上或滾到學校置物櫃前等奇怪的地方。

為了測試鹿乃子乃子的翻滾能力，虎視虎子在草地上選擇了 $N$ 個不同的位置 $(x_{i}, y_{i})$ 。一開始她會在第一個位置擺放鹿仙貝，當目前擺放的鹿仙貝被鹿乃子乃子吃掉後，虎視虎子便會馬上在下一個位置擺放鹿仙貝，直到 $N$ 個位置的鹿仙貝都被吃掉為止。

而鹿乃子乃子也會從第一個位置出發。每次進行翻滾時，她會選擇一個終點，從起點沿著直線方向一路滾到終點。終點的位置不需要是 $N$ 個位置的其中之一，可以是草地上的任意一個位置。如果滾的途中經過的位置有鹿仙貝，她會吃掉鹿仙貝並繼續滾。當一次翻滾結束後，如果她還沒有吃掉 $N$ 塊鹿仙貝，則她會以這次翻滾的終點作為下一次翻滾的起點，並選擇新的終點繼續下一次的翻滾。

為了讓鹿乃子乃子滾久一點，好讓自己跟姐姐有更久的相處時間，虎視餡子打算重新安排這 $N$ 個位置的順序，讓鹿乃子乃子進行翻滾的次數越多越好。不過鹿乃子乃子在知道了 $N$ 個位置的順序後，會使用超級電腦「鹿岳」進行計算，並透過鹿角接收計算結果，選擇能夠進行最少次翻滾的方式吃掉所有的鹿仙貝。

你能寫一支程式幫助虎視餡子安排順序嗎？

Input Format

輸入的第一行為一整數 $T$ ，表示測試資料的數量。

每一筆測試資料第一行為一整數 $N$ 。接下來 $N$ 行，每行包含兩個整數 $x_{i}, y_{i}$ ，表示第 $i$ 個位置的座標。

$1 \leq T \leq 10^{4}$
$1 \leq N \leq 10^{6}$
$- 10^{9} \leq x_{i}, y_{i} \leq 10^{9}$
$(x_{i}, y_{i}) \neq (x_{j}, y_{j}), \forall i \neq j$
保證測試資料中 $N$ 的總和不超過 $10^{6}$

Output Format

對於每一筆測試資料，第一行請輸出一整數 $X$ ，表示鹿乃子乃子要進行多少次翻滾才能吃到 $N$ 塊鹿仙貝。第二行請輸出 $N$ 個整數 $a_{1}, a_{2}, \dots, a_{N}$ ，其中 $a_{i}$ 表示重新安排順序後，第 $i$ 個位置為原本的第 $a_{i}$ 個位置，也就是 $(x_{a_{i}}, y_{a_{i}})$ 。

如果有多種可能的輸出，你可以輸出任意一種。

每個位置必須恰好出現一次

Sample Input 1

3
3
0 0
0 1
1 0
5
2 0
1 1
2 2
0 0
0 2
1
-45510 45510

Sample Output 1

Hints

第一筆範例測資中，鹿乃子乃子可能選擇的滾動方式如下：從 $(0, 0)$ 出發，第 $1$ 次翻滾選擇終點 $(1, 0)$ ，第 $2$ 次翻滾選擇終點 $(0, 0)$ ，在 $2$ 次翻滾後吃完所有鹿仙貝。可以證明不存在安排順序的方式會讓鹿乃子乃子使用 $3$ 次或更多的翻滾才能吃完所有鹿仙貝。

第二筆範例測資中，鹿乃子乃子可能選擇的滾動方式如下：從 $(0, 0)$ 出發，依序選擇 $(2.5, 2.5)$ 、 $(0, 2)$ 、 $(2, 0)$ 、 $(1, 1)$ 作為翻滾的終點，在 $4$ 次翻滾後吃完所有鹿仙貝。

注意到雖然第 $1$ 次及第 $3$ 次翻滾會經過 $(1, 1)$ 的位置，但該位置的鹿仙貝要等到吃完 $(2, 0)$ 的鹿仙貝才會出現。另外，鹿乃子乃子選擇的滾動的終點也不須是 $N$ 個位置的其中之一，可以選擇任意位置作為終點。

第三筆範例測資中只有一個位置，鹿乃子乃子不須翻滾就可以在起點吃到鹿仙貝。

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	1~10	保證測試資料中 $N$ 的總和不超過 $8$	5
3	0~23	保證測試資料中 $N$ 的總和不超過 $1000$	10
4	24~31	保證 $N$ 是完全平方數且 $1 \leq x_{i}, y_{i} \leq \sqrt{N}$	20
5	0~43	無額外限制	65

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	262144	65536	1 3 5
1	1000	262144	65536	2 3 5
2	1000	262144	65536	2 3 5
3	1000	262144	65536	2 3 5
4	1000	262144	65536	2 3 5
5	1000	262144	65536	2 3 5
6	1000	262144	65536	2 3 5
7	1000	262144	65536	2 3 5
8	1000	262144	65536	2 3 5
9	1000	262144	65536	2 3 5
10	1000	262144	65536	2 3 5
11	1000	262144	65536	3 5
12	1000	262144	65536	3 5
13	1000	262144	65536	3 5
14	1000	262144	65536	3 5
15	1000	262144	65536	3 5
16	1000	262144	65536	3 5
17	1000	262144	65536	3 5
18	1000	262144	65536	3 5
19	1000	262144	65536	3 5
20	1000	262144	65536	3 5
21	1000	262144	65536	3 5
22	1000	262144	65536	3 5
23	1000	262144	65536	3 5
24	1000	262144	65536	4 5
25	1000	262144	65536	4 5
26	1000	262144	65536	4 5
27	1000	262144	65536	4 5
28	1000	262144	65536	4 5
29	1000	262144	65536	4 5
30	1000	262144	65536	4 5
31	1000	262144	65536	4 5
32	1000	262144	65536	5
33	1000	262144	65536	5
34	1000	262144	65536	5
35	1000	262144	65536	5
36	1000	262144	65536	5
37	1000	262144	65536	5
38	1000	262144	65536	5
39	1000	262144	65536	5
40	1000	262144	65536	5
41	1000	262144	65536	5
42	1000	262144	65536	5
43	1000	262144	65536	5

Submit out of contest

1 . 一鹿順風