Задача G. Мосты-горки

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Выбор подходящего проекта строительства моста на остров Русский — задача не из лёгких: ведь существует много разновидностей мостов.

В Академии был разработан новый тип мостов — мосты-горки. Эти мосты устанавливаются между двумя островами, один из которых должен быть высоким, а другой низким. Чтобы попасть с высокого острова на низкий, достаточно просто скатиться по мосту, как по горке. При этом даже не нужно тратить топливо! К тому же при достаточной массе автомобиля езда превращается в увлекательный аттракцион.

Но у мостов-горок есть и недостатки:

  1. Мост должен быть идеально прямым: массивные автомобили могут не справиться с поворотами на большой скорости.
  2. Конструкция мостов-горок такова, что один мост не может проходить над другим мостом, то есть мосты не должны пересекаться друг с другом.

Ввиду заинтересованности правительства в мостах-горках в Академии была организована лаборатория по их исследованию. В лабораторных условиях была создана модель архипелага, в котором N высоких и N низких островов представлены точками на плоскости, причём никакие три острова не лежат на одной прямой. Требуется построить ровно N мостов-горок между островами так, чтобы на каждом острове был мост. Как высокие, так и низкие острова пронумерованы от 1 до N.

Первый пример теста соответствует рисунку справа. Тёмными изображены острова с номером 1, а светлыми — с номером 2. Если соединить тёмные острова со светлыми, то мосты будут пересекаться.

Формат входного файла

Входной содержит число N, за которым следует N пар чисел Xi Yi — координаты высоких островов, а затем N пар чисел xi yi — координаты низких островов.

Формат выходного файла

Выходной файл должен содержать N пар чисел pi qi — номера островов, соединённых мостом, где pi — номер высокого острова, qi — номер низкого острова. Пары можно выводить в произвольном порядке. Если решений несколько, выведите любое из них.

Если N мостов-горок построить невозможно, то выходной файл должен содержать единственное число 1.

Ограничения

1 ≤ N ≤ 1000, 105 ≤ Xi, Yi, xi, yi ≤ 105.

Все числа во входном файле целые.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
0 0
1 0
-2 -3
2 -3
1 1
2 2
2
5
1 0
2 2
-1 0
0 -3
-2 -3
4 -2
2 -2
1 -1
-1 -1
-3 2
1 3
4 1
2 2
5 4
3 5

0.042s 0.007s 17