CF1508D.Swap Pass

Based on a peculiar incident at basketball practice, Akari came up with the following competitive programming problem!

You are given $n$ points on the plane, no three of which are collinear. The $i$-th point initially has a label $a_i$, in such a way that the labels $a_1, a_2, \dots, a_n$ form a permutation of $1, 2, \dots, n$.

You are allowed to modify the labels through the following operation:

1. Choose two distinct integers $i$ and $j$ between $1$ and $n$.
2. Swap the labels of points $i$ and $j$, and finally
3. Draw the segment between points $i$ and $j$.

A sequence of operations is valid if after applying all of the operations in the sequence in order, the $k$-th point ends up having the label $k$ for all $k$ between $1$ and $n$ inclusive, and the drawn segments don't intersect each other internally. Formally, if two of the segments intersect, then they must do so at a common endpoint of both segments.

In particular, all drawn segments must be distinct.

Find any valid sequence of operations, or say that none exist.

基于篮球训练中发生的一起奇特事件，Akari 提出了如下一道编程竞赛题目！

给定平面上的 $n$ 个点，其中任意三点不共线。第 $i$ 个点初始时标有标签 $a_i$，且标签序列 $a_1, a_2, \dots, a_n$ 构成 $1, 2, \dots, n$ 的一个排列。

你可通过以下操作修改各点的标签：

1. 选择两个互异的整数 $i$ 和 $j$，满足 $1 \le i, j \le n$；
2. 交换第 $i$ 个点与第 $j$ 个点的标签；
3. 最后，连接第 $i$ 个点与第 $j$ 个点，画出一条线段。

若一个操作序列满足：按顺序执行该序列中所有操作后，对每个 $k = 1, 2, \dots, n$，第 $k$ 个点的标签恰好为 $k$，且所画出的所有线段两两之间内部不相交（即：若两条线段相交，则交点必须是它们的公共端点），则称该序列是合法的。

特别地，所有画出的线段必须互不相同。

请找出任意一个合法的操作序列；若不存在这样的序列，请说明不存在。

The first line contains an integer $n$ ($3 \le n \le 2000$) — the number of points.

The $i$-th of the following $n$ lines contains three integers $x_i$, $y_i$, $a_i$ ($-10^6 \le x_i, y_i \le 10^6$, $1 \le a_i \le n$), representing that the $i$-th point has coordinates $(x_i, y_i)$ and initially has label $a_i$.

It is guaranteed that all points are distinct, no three points are collinear, and the labels $a_1, a_2, \dots, a_n$ form a permutation of $1, 2, \dots, n$.

第一行包含一个整数 $n$（$3 \le n \le 2000$），表示点的数量。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i$、$y_i$、$a_i$（$-10^6 \le x_i, y_i \le 10^6$，$1 \le a_i \le n$），表示第 $i$ 个点的坐标为 $(x_i, y_i)$，且初始标签为 $a_i$。

保证所有点互不相同，任意三点不共线，且标签 $a_1, a_2, \dots, a_n$ 构成 $1, 2, \dots, n$ 的一个排列。

If it is impossible to perform a valid sequence of operations, print $-1$.

Otherwise, print an integer $k$ ($0 \le k \le \frac{n(n - 1)}{2}$) — the number of operations to perform, followed by $k$ lines, each containing two integers $i$ and $j$ ($1 \le i, j \le n$, $i\neq j$) — the indices of the points chosen for the operation.

Note that you are not required to minimize or maximize the value of $k$.

If there are multiple possible answers, you may print any of them.

如果无法执行有效的操作序列，请输出 $-1$。

否则，先输出一个整数 $k$（$0 \le k \le \frac{n(n - 1)}{2}$）—— 表示需要执行的操作次数，然后输出 $k$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i, j \le n$，且 $i\neq j$）—— 表示该次操作所选点的下标。

注意：你无需最小化或最大化 $k$ 的值。

若存在多个可能的答案，你可以输出其中任意一个。

The following animation showcases the first sample test case. The black numbers represent the indices of the points, while the boxed orange numbers represent their labels.

In the second test case, all labels are already in their correct positions, so no operations are necessary.

以下动画展示了第一个样例测试用例。黑色数字表示点的索引，带橙色方框的数字表示它们的标签。

在第二个测试用例中，所有标签均已处于正确位置，因此无需执行任何操作。