Остров народа Флатопии представляет собой часть плоскости. К сожалению, во Флатопии очень плохая система дорог. Правительство беспокоится об этой проблеме и уже построило несколько дорог, соединяющих наиболее важные города. Как всегда, остались города, до которых невозможно добраться по дорогам. Требуется построить новые дороги так, чтобы можно было проехать по дорогам от любого города до любого другого.
Города во Флатопии пронумерованы от 1 до N и город с номером i имеет декартовы координаты (x
i, y
i). Каждая дорога соединяет ровно два города. Все дороги (уже построенные и те, которые собираются построить) лежат на прямых линиях и их длина равна декартовому расстоянию между городами. Все дороги имеют двухстороннее движение. Дороги могут пересекаться, но водитель может переезжать с дороги на дорогу только в городах.
Правительство Флатопии хочет минимизировать стоимость постройки новых дорог. При этом, они хотят, чтобы все города были достижимы по дорогам. Так как Флатопия является плоской, то стоимость постройки дороги пропорциональна её длине. Поэтому, в целях экономии, требуется минимизировать суммарную длину построенных дорог.
Входные данные
Входной файл состоит из двух частей. Первая часть содержит информацию о городах Флатопии, а вторая о дорогах, которые уже построены.
Первая строка входного файла содержит единственное целое число N (1 <= N <= 750), обозначающее число городов. Следующие N строк содержат по два целых числа, x
i и y
i, разделённых пробелом. Эти числа являются координатами соответствующих городов (для i от 1 до N). Координаты по модулю не превосходят 10000. Никакие два города не совпадают.
Следующая строка содержит одно число M (0 <= M <= 1000), представляющее количество уже построенных дорог. Следующие M строк содержат по два целых числа, разделённых пробелом. Эти два числа обозначают пару городов, которые уже соединены дорогами. Каждая пара соединена не более чем одной дорогой.
Выходные данные
В выходной файл выведите дороги, имеющие минимальную возможную суммарную длину, которые требуется построить для соединения всех городов. Каждая дорога должна быть записана на отдельной строке в виде номеров соединённых городов, записанных через пробел. Если дорог строить не нужно, то выходной файл должен быть создан, но при этом остаться пустым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2
|
1 6
4 9
5 7
8 3
7 3
|