Задачи
Пары
Пары
На дипломатическом приёме находится \textbf{N} дипломатов, причём число \textbf{N} чётно. Каждый дипломат ведё беседу ровно с одним другим дипломатом. Разведке одной из стран удалось получить фотографии с приёма. Изучив эти фотографии, аналитики установили координаты каждого из дипломатов и попытались восстановить, кто из них с кем беседует. Алгоритм восстановления следующий: из дипломатов, ещё не распределённых по парам, выбираются двое, расстояние между которыми минимально, и принимается, что они беседуют между собой. В случае, если существует несколько пар дипломатов, у которых растояния минимальны, вибирается пара с лексикографически наименьшим номером (все дипломаты пронумерованы по номерам их досье в разведке от \textbf{1} до \textbf{N}, внутри пары собеседников дипломат с нименьшим номером указывается первым).
Вам поручено реализовать этот алгоритм.
\InputFile
Первая строка входного файла содержит чётное число \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{300}). В последующих \textbf{N} строках заданы координаты \textbf{x}_i и \textbf{y}_i каждого дипломата, причём в \textbf{i}-й строке заданы координаты дипломата с номером досье \textbf{i}. Для различных дипломатов как минимум одна из существующих координат различна. Координаты не превосходят по абсолютной величине \textbf{10}^8.
\OutputFile
Выведите \textbf{N}/\textbf{2} строк - номера пар дипломатов, беседующих между собой. Пары выводятся в лексикографическом порядке, внутри каждой пары первое число должно быть меньше второго.
Входные данные #1
6 0 2 3 2 0 0 1 0 0 -2 2 -2
Выходные данные #1
1 2 3 4 5 6