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

Ограничение по времени: 1 секунда

Лука смог приобрести всю коллекцию динозавров из «Шестёрочки» и обнаружил, что в динозаврах есть коммутаторы, поэтому ему захотелось объединить их в одну локальную сеть. Он расставил на декартовой плоскости всю коллекцию, то есть местоположение каждого динозавра задана двумя числами — координатами по осям x и y.
Лука хочет соединить их проводами так, чтобы между любыми двумя динозаврами существовал путь по этим проводам. Луку раздражают спутанные провода, поэтому никакие два провода не должны пересекаться (пересечения в концах отрезков разрешены). Кроме того, у Луки мало денег на покупку проводов, поэтому общее количество проведённых отрезков не должно превышать 2n.

Формат входных данных
Первая строка содержит одно целое число n (1≤n≤103) — количество динозавров.
В следующих 2n строках заданы координаты динозавров. В каждой строке записано одно целое число: первая строка содержит координату по оси x для первого динозавра, вторая строка — координату по оси y для первого динозавра, третья строка — координату по оси x для второго динозавра, и так далее. Таким образом, координата xi для i-го динозавра находится в (2i)-й строке входных данных, координата yi для i-го динозавра находится в (2i+1)-й строке входных данных. Гарантируется, что (−109≤xi,yi≤109), а также никакие два динозавра не находятся в одной точке плоскости.

Формат выходных данных
В первой строке выведите одно число 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

1

Скиньте кто решил

0