В связи со специфическим инцидентом на баскетбольной тренировке, Akari придумал следующую задачу со спортивного программирования!
Вам даны \(n\) точек на плоскости, никакие три из которых не лежат на одной прямой. Изначально точка \(i\) имеет метку \(a_i\), причем метки \(a_1, a_2, \dots, a_n\) образуют перестановку чисел \(1, 2, \dots, n\).
Вы можете менять эти метки с помощью следующей операции:
- Выберите два разных целых числа \(i\) и \(j\) между \(1\) и \(n\).
- Поменяйте местами метки точек \(i\) и \(j\).
- Нарисуйте отрезок между точками \(i\) и \(j\).
Последовательность операций корректна, если после применения всех операций в последовательности точка \(k\) имеет метку \(k\) для всех \(k\) от \(1\) до \(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\).
Если возможных ответов несколько, вы можете вывести любой из них.
Примечание
Следующая анимация демонстрирует первый пример. Черные числа обозначают номера точек, а оранжевые — их метки.
Во втором примере все метки изначально находятся в правильном положении, поэтому никаких операций не требуется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
3
5 4 1
0 0 2
-3 -2 3
|
0
|