eolymp
bolt
Try our new interface for solving problems

Пары

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

На дипломатическом приёме находится N дипломатов, причём число N чётно. Каждый дипломат ведё беседу ровно с одним другим дипломатом. Разведке одной из стран удалось получить фотографии с приёма. Изучив эти фотографии, аналитики установили координаты каждого из дипломатов и попытались восстановить, кто из них с кем беседует. Алгоритм восстановления следующий: из дипломатов, ещё не распределённых по парам, выбираются двое, расстояние между которыми минимально, и принимается, что они беседуют между собой. В случае, если существует несколько пар дипломатов, у которых растояния минимальны, вибирается пара с лексикографически наименьшим номером (все дипломаты пронумерованы по номерам их досье в разведке от 1 до N, внутри пары собеседников дипломат с нименьшим номером указывается первым).

Вам поручено реализовать этот алгоритм.

Giriş verilənləri

Первая строка входного файла содержит чётное число N (2N300). В последующих N строках заданы координаты x_i и y_i каждого дипломата, причём в i-й строке заданы координаты дипломата с номером досье i. Для различных дипломатов как минимум одна из существующих координат различна. Координаты не превосходят по абсолютной величине 10^8.

Çıxış verilənləri

Выведите N/2 строк - номера пар дипломатов, беседующих между собой. Пары выводятся в лексикографическом порядке, внутри каждой пары первое число должно быть меньше второго.

Nümunə

Giriş verilənləri #1
6
0 2
3 2
0 0
1 0
0 -2
2 -2
Çıxış verilənləri #1
1 2
3 4
5 6