Трилобит очень любит строить метро. Он спроектировал $n$ линий, для каждой из которых выбрано по $n+1$ потенциальных станций, заданных координатами на плоскости.
Чтобы сделать поездки на метро более разнообразными, Трилобит решил, что каждая линия будет представлять собой отрезок! Это означает, что для каждой линии Трилобит выберет только две станции и соединит их отрезком. Чтобы максимизировать неудобство пересадок для пассажиров, Трилобит требует, чтобы количество попарных пересечений между $n$ построенными линиями метро было минимальным. Заметьте, что пересечения включают в себя начальные и конечные станции. Пожалуйста, спланируйте допустимую схему.
Простыми словами: даны $n$ цветов точек, по $n+1$ точек каждого цвета на двумерной плоскости. Требуется выбрать по две различные точки для каждого цвета и соединить их отрезком так, чтобы общее количество попарных пересечений всех $n$ отрезков было минимальным. Выведите конструктивное решение.
Примечание: если два отрезка лежат на одной прямой, количество их пересечений считается бесконечным. Все бесконечности считаются равными.
Входные данные
Задача содержит несколько наборов входных данных. В первой строке задано целое положительное число $T$ — количество наборов данных. Для каждого набора данных:
В первой строке задано целое положительное число $n$ — количество линий.
Далее следуют $n$ строк, каждая из которых содержит $2n+2$ целых чисел. Числа на позициях $2i-1$ и $2i$ задают координаты $(x_i, y_i)$ $i$-й станции текущей линии, где $i$ — номер станции.
Гарантируется, что все координаты станций различны.
Выходные данные
Для каждого набора данных выведите $n$ строк, каждая из которых содержит два целых числа — номера станций, соединенных соответствующей линией. Вы можете вывести любой подходящий вариант.
Примеры
Входные данные 1
1 2 5 0 0 8 10 8 0 4 10 4 5 12
Выходные данные 1
1 3 1 3
Примечание
На рисунке синие и красные точки обозначают станции первой и второй линий соответственно, а синяя и красная линии — выбранные отрезки для первой и второй линий.
Заметьте, что вам нужно вывести только один из возможных вариантов, поэтому:
1 2 2 3
также является правильным ответом.
Подзадачи
| Номер подзадачи | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 30 | $n\le 5, \sum n\le 50$ |
| 2 | 20 | Существует такая перестановка этих $n(n+1)$ точек, что координаты $i$-й точки равны $(i, i)$ |
| 3 | 20 | $n\leq 100$ |
| 4 | 30 | Нет |
Для всех данных: $1\le n\le 1000, \sum n\leq 2000$, $|x_i|, |y_i|\le 10^9$.