D. Обмены на ребрах
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В связи со специфическим инцидентом на баскетбольной тренировке, Akari придумал следующую задачу со спортивного программирования!

Вам даны $$$n$$$ точек на плоскости, никакие три из которых не лежат на одной прямой. Изначально точка $$$i$$$ имеет метку $$$a_i$$$, причем метки $$$a_1, a_2, \dots, a_n$$$ образуют перестановку чисел $$$1, 2, \dots, n$$$.

Вы можете менять эти метки с помощью следующей операции:

  1. Выберите два разных целых числа $$$i$$$ и $$$j$$$ между $$$1$$$ и $$$n$$$.
  2. Поменяйте местами метки точек $$$i$$$ и $$$j$$$.
  3. Нарисуйте отрезок между точками $$$i$$$ и $$$j$$$.

Последовательность операций корректна, если после применения всех операций в последовательности точка $$$k$$$ имеет метку $$$k$$$ для всех $$$k$$$ от $$$1$$$ до $$$n$$$ включительно, и нарисованные отрезки не пересекаются внутри друг друга. Формально, если два отрезка пересекаются, то они должны сделать это в общей конечной точке обоих отрезков.

В частности, все нарисованные отрезки должны быть попарно различными.

Найдите любую корректную последовательность операций или определите, что ее нет.

Входные данные

В первой строке содержится целое число $$$n$$$ ($$$3 \le n \le 2000$$$)  — количество точек.

В $$$i$$$-й из следующих $$$n$$$ строк содержится три целых числа $$$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$$$.

Выходные данные

Если невозможно выполнить корректную последовательность операций, выведите $$$-1$$$.

В противном случае выведите целое число $$$k$$$ ($$$0 \le k \le \frac{n(n - 1)}{2}$$$)  — количество выполняемых операций, а затем $$$k$$$ строк, каждая из которых содержит два целых числа $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i\neq j$$$)  — номера точек, выбранных для операции.

Обратите внимание, что вам не требуется минимизировать или максимизировать значение $$$k$$$.

Если возможных ответов несколько, вы можете вывести любой из них.

Примеры
Входные данные
5
-1 -2 2
3 0 5
1 3 4
4 -3 3
5 2 1
Выходные данные
5
1 2
5 3
4 5
1 5
1 3
Входные данные
3
5 4 1
0 0 2
-3 -2 3
Выходные данные
0
Примечание

Следующая анимация демонстрирует первый пример. Черные числа обозначают номера точек, а оранжевые — их метки.

Во втором примере все метки изначально находятся в правильном положении, поэтому никаких операций не требуется.