Problems
Пары точек
Пары точек
На плоскости своими координатами заданы \textbf{n }красных и \textbf{n }синих точек. Никакие три точки не принадлежат одной прямой. Необходимо построит \textbf{n }отрезков таких, что никакие два из них не пересекаются, кажды отрезок соединяет точки разного цвета, и каждая точка принадлежит ровно одному отрезку.
Напишите программу, которая по информации о размещении точек найдёт любое разбиение множества точек на \textbf{n }отрезков, каждый из которых соединяет синюю и красную точки. Причём, каждая точка принадлежит только одному отрезку и никакие два отрезка не пересекаются.
\InputFile
Первая строка содержит количество тестов, которые идут один за другим. Первая строка каждого тестоа содержит количество точек \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{2500}) одного цвета. Далее идут наборы координат синих точек, а потом -- красных. Набор координат точек одного цвета задаётся \textbf{n }строками, каждая из которых содержит пару целых чисел \textbf{x }и \textbf{y} (\textbf{|x|} ≤ \textbf{10000}, \textbf{|y| }≤ \textbf{10000})\textbf{ }- координаты точки.
\OutputFile
Вывести ответы для всех тестов без разделения. Каждая из \textbf{n }строк ответа каждого из блоков должна содержать пару целых чисел от \textbf{1 }до \textbf{n }- номера синей и красной точек соединённых отрезком. Точки пронумерованы в том порядке, в котором они идут на входе отдельно по каждому цвету. В случае, если невозможно соединить точки отрезками без пересечений, единственная строка ответа для блока должна содержать число \textbf{0}.
Input example #1
2 6 -1 4 0 0 1 7 4 6 9 4 8 0 3 5 5 1 6 5 8 3 2 6 0 3 5 -1 4 0 0 3 5 8 0 9 4 1 7 4 6 5 1 6 5 8 3
Output example #1
2 1 1 6 3 5 4 2 6 3 5 4 1 1 5 2 4 5 3 4 2 3