캠퍼스 연결하기

폴카루 대학교(University of Polkaroo) 캠퍼스에 새 건물이 여러 채 지어지고 있다. 대학은 모든 건물이 통신 케이블 네트워크를 통해 (직접 또는 간접적으로) 서로 연결되기를 원한다.

각 건물은 $x$ 좌표와 $y$ 좌표로 주어지는 평면 위의 한 점으로 나타낸다. 통신 케이블 하나는 정확히 두 건물을 잇는 선분이며, 정보는 케이블을 따라 양방향으로 전달된다. 케이블끼리는 자유롭게 교차할 수 있지만, 오직 끝점(건물)에서만 서로 연결된다.

캠퍼스 지도에는 모든 건물의 위치와 이미 설치된 통신 케이블이 표시되어 있다. 기존 케이블은 바꿀 수 없다. 모든 건물이 연결되도록 새 통신 케이블을 설치하되, 새로 사용하는 케이블의 총 길이를 최소로 하려고 한다.

입력은 하나의 테스트 케이스를 나타낸다. 첫 줄에는 건물의 수 $N$ $(1 \le N \le 750)$이 주어진다. 건물은 $1$번부터 $N$번까지 번호가 매겨져 있다. 이어지는 $N$개의 줄에는 각 건물의 $x$ 좌표와 $y$ 좌표가 주어진다. 좌표는 절댓값이 $10,000$ 이하인 정수이며, 같은 위치에 있는 두 건물은 없다.

그다음 줄에는 기존 케이블의 수 $M$ $(0 \le M \le 1000)$이 주어지고, 이어지는 $M$개의 줄에 각 기존 케이블이 직접 잇는 두 건물의 번호가 주어진다. 같은 두 건물을 직접 잇는 케이블은 최대 한 개뿐이다.

새로 설치하는 케이블의 총 길이의 최솟값을 소수점 아래 둘째 자리까지 반올림하여 한 줄에 출력한다.