A14236 | 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.

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$ .

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.