题目描述

$20$世纪末最激动人心的太空发现发生在$Y1999$星球。$1999$年，科学家在该星球发现了一种类似蚂蚁的生物，命名为$M11$。它的头部左侧只有一只眼睛，右侧身体有三只脚，并受到以下三个行走限制：

$1$.由于特殊的身体结构，它无法右转。

$2$.行走时会留下红色路径。

$3$.它讨厌重复走过已染红的路径，且绝不再犯。

由"发现号"宇宙飞船传回的图片显示，$Y1999$星球的植物生长在特殊的坐标点上。通过分析数千张图片，科学家发现了一个支配植物生长点的神奇坐标系。在这个坐标系中，没有两个植物共享相同的$x$或$y$坐标。

$M11$每天必须吃恰好一株植物才能存活。当它吃掉一株植物后，当天会停留在原地不再移动。次日，它会寻找另一株植物并前往进食。如果无法到达任何其他植物，它将在当天结束时死亡。注意，它可以到达任意距离的植物。

问题是要为$M11$找到一条路径，使其存活时间最长。

输入是一组植物的$(x, y)$坐标。假设$A$是$y$坐标最小的植物，$M11$从点$(0, y_A)$出发，朝向植物$A$。路径不能自交，所有转弯必须为逆时针方向。注意，路径可能访问同一直线上的多个植物。

输入

输入的第一行是$M$，表示测试用例数量（$1 \leq M \leq 10$）。每个测试用例的第一行是$N$（植物数量，$1 \leq N \leq 50$），随后是$N$行植物数据。每行包含三个整数：植物唯一编号（$1..N$），以及坐标$x$和$y$。植物按输入顺序编号递增排列，坐标值不超过$100$。

输出

每个测试用例输出一行，包含路径长度和访问植物的编号序列。

输入数据1

2
10
1 4 5
2 9 8
3 5 9
4 1 7
5 3 2
6 6 3
7 10 10
8 8 1
9 2 4
10 7 6
14
1 6 11
2 11 9
3 8 7
4 12 8
5 9 20
6 3 2
7 1 6
8 2 13
9 15 1
10 14 17
11 13 19
12 5 18
13 7 3
14 10 16

输出数据1

10 8 7 3 4 9 5 6 2 1 10
14 9 10 11 5 12 8 7 6 13 4 14 1 3 2

来源

德黑兰1999竞赛