410525: GYM104034 5 Лука и локальная сеть динозавров

5. Лука и локальная сеть динозавровограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Лука смог приобрести всю коллекцию динозавров из «Шестерочки» и обнаружил, что в динозаврах есть коммутаторы, поэтому ему захотелось их объединить в одну локальную сеть.

Он расставил на декартовой плоскости всю коллекцию, то есть местоположение каждого динозавра задано двумя числами — координатами по оси $$$x$$$ и $$$y$$$.

Лука хочет соединить их проводами так, чтобы между любыми двумя динозаврами существовал путь по этим проводам. Луку раздражают спутанные провода, поэтому никакие два провода не должны пересекаться (пересечения в концах отрезков разрешены). Кроме того, у Луки мало денег на покупку проводов, поэтому общее количество проведенных отрезков не должно превышать $$$2n$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^3$$$) — количество динозавров.

В следующих $$$2n$$$ строках заданы координаты динозавров. В каждой строке записано одно целое число: первая строка содержит координату по оси $$$x$$$ для первого динозавра, вторая строка — координату по оси $$$y$$$ для первого динозавра, третья строка — координату по оси $$$x$$$ для второго динозавра, и так далее. Таким образом координата $$$x_i$$$ для $$$i$$$-го динозавра находится $$$(2i)$$$-й строке входных данных, координата $$$y_i$$$ для $$$i$$$-го динозавра находится в $$$(2i + 1)$$$-й строке входных данных. Гарантируется, что $$$(-10^9 \le x_i, y_i \le 10^9)$$$, а также никакие два динозавра не находятся в одной точке плоскости.

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

В первой строке выведите одно число $$$m$$$ — количество проведенных проводов, либо число $$$-1$$$, если соединить динозавров описанным в условии способом невозможно.

Если существует подходящее под условие соединение, то в следующих $$$m$$$ строках выведите по два целых числа — порядковые номера динозавров, соединенных очередным проводом.

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

Система оценки

Решения, правильно работающие только для случаев, когда $$$n$$$ не превосходит $$$4$$$, будут оцениваться в $$$25$$$ баллов.

Решения, правильно работающие только для случаев, когда никакие три динозавра не лежат на одной прямой, будут оцениваться в $$$25$$$ баллов.

Решения, правильно работающие только для случаев, когда у всех динозавров координаты по оси $$$x$$$ различны, будут оцениваться в $$$25$$$ баллов.

ПримерыВходные данные

6
8
7
-8
6
-7
-3
9
-3
6
2
4
1

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

7
1 2
1 5
2 3
2 6
3 6
3 4
4 5

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

3
-3
4
8
-4
-1
0

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

2
1 3
3 2

Примечание

Иллюстрация ответа для первого примера из условия: