Рабочее место участника

В королевство Ксант добрался технический прогресс, и король решил построить сеть двухсторонних автомобильных и железных дорог, связывающую все города страны. На случай забастовок водителей автобусов или машинистов паровозов король решил, что между любыми городами страны можно будет проехать, двигаясь только по автомобильным дорогам или только по железным дорогам. Кроме того, железная дорога не должна дублировать автомобильную и наоборот, т.е. если из города `i` в город `j` ведет автомобильная дорога, то между этими городами не должно быть железной дороги, и наоборот. Король хочет минимизировать расходы на строительство сети дорог. Стоимости строительства километра автомобильной и железной дороги равны. Дороги могут начинаться и заканчиваться только в городах, дороги вне городов волшебным образом проходят друг над другом без пересечения.

Напишите программу, которая определяет между какими городами какой вид дороги должен быть построен, чтобы суммарная стоимость строительства сети дорог была минимальной.

Первая строка ввода содержит одно целое число `N` (`4\ ≤\ N\ ≤\ 1000`) – количество городов в стране. Далее следует `N` строк содержащих по два целых числа `X_i` и `Y_i` (`0\ ≤\ X_i,\ Y_i\ ≤\ 1000`) – координаты городов. Никакие три города в стране не расположены на одной прямой.

Вывести `(N-1)` строку, содержащих по два числа – номера городов, соединяемых автомобильной дорогой. Затем вывести `(N-1)` строку, содержащих по два числа – номера городов, соединяемых железной дорогой.

4
0 0
100 100
0 100
100 0

1 2
2 3
3 4
1 3
1 4
2 4