Дано кілька точок на площині, деякі з яких з'єднані відрізками. Безліч точок називаються зв'язними, якщо з будь-якої точки можна перейти в будь-яку точку, переміщаючись тільки по відрізках (переходити з відрізка на відрізок можливо тільки в точках вихідної множини).

Можна за певну плату додавати нові відрізки (вартість додавання дорівнює довжині відрізка, що додається). Потрібно за мінімальну вартість зробити цю множину зв'язною.

Формат вхідних даних

У першому рядку вхідних даних міститься одне ціле число \(𝑁\) (\(1 ≤ 𝑁 ≤ 50\)) – кількість точок.

Далі в \(𝑁\) рядках записано по 2 натуральні числа – координати точок (координати не перевищують 100). Усі точки різні.

Далі дано число \(𝑀\) – кількість відрізків, що вже існують.

У наступних \(𝑀\) рядках записано по 2 числа – номери початку та кінця відповідного відрізка.

Формат вихідних даних

Вивести єдине число – мінімально можливу вартість доповнення з точністю 5 знаків після коми.

Приклад вхідних даних

3
1 1
1 2
10 1
1
2 1

Приклад вихідних даних

9.0