P14511 [NFLSPC #8] 轨道交通


三叶虫非常喜欢建造地铁。他设计了 $n$ 条线路，每条线路均有 $n+1$ 个站点选址，用平面上的坐标表示。 为了丰富地铁体验，三叶虫决定每条线路都是一条线段！也就是说，对于对于每条线路，三叶虫仅会选择**两个站点**，在这两个站点之间连一条线段。为了最大化乘客换乘的麻烦程度，三叶虫要求建立的 $n$ 条地铁之间两两交点个数最少。注意交点包含起点和终点站。请你规划一种合法的方案。 --- 人话：给定二维平面上 $n$ 种颜色的点各 $n+1$ 个。要求在每种颜色中选出两个不同的点连一条线段，且所有 $n$ 条线段两两交点个数最少。输出构造方案。 **注意：如果两条线段共线，交点数定义为无穷大。所有无穷大认为相等。**

本题有多组测试数据，第一行一个正整数 $T$ 表示数据组数，对于每一组测试数据： 第一行一个正整数 $n$ 表示线路的数量。 接下来 $n$ 行每行 $2n+2$ 个整数，其中第 $2i-1$ 个和第 $2i$ 个整数 $(x_i,y_i) $ 标识了当前路线一个站点的坐标，且该站点的标号为 $i$。 保证所有的站点坐标互不相同。

对于每一组测试数据，输出 $n$ 行每行两个正整数，依次表示每条线路连接的两个站点的标号。你只需要输出任意解。

### 样例解释  图中蓝色和红色的点分别表示一号线和二号线的站点，蓝线和红线分别表示一号线和二号线选择的线路。 注意你只需要输出任意解，即 ``` 1 2 2 3 ``` 也是正确答案。 ### 数据范围 | 子任务编号 | 分值 | 额外限制 | |:--:|:--:|:--:| | 1 | 30 | $n\le 5,\sum n\le 50$ | | 2 | 20 | 存在一种排列这 $n(n+1)$ 个点的方案使得第 $i$ 个点的坐标恰为 $(i,i)$ | | 3 | 20 | $n\leq 100$ | | 4 | 30 | 无 | 对于所有数据：$1\le n\le1000,\sum n\leq 2000$，$|x_i|,|y_i|\le10^9$。