Даны несколько точек на плоскости, некоторые из которых соединены отрезками. Множество точек называется связанным, если из любой его точки можно перейти в любую точку, перемещаясь только по отрезкам (переходить с отрезка на отрезок возможно только в точках исходного множества). Можно за определенную плату добавлять новые отрезки (стоимость добавления равна длине добавляемого отрезка). Требуется за минимальную стоимость сделать данное множество связанным.
Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.
Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения с точностью 5 знаков после запятой.
Примеры
Входные данные
3
1 1
1 2
10 1
1
2 1
Выходные данные
9.0
Опубликован 03.03.2016 в 19:40 Последнее изменение: 03.03.2016 в 19:44