근거리 네트워크

문제 정보

문제

근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일부 건물들만이 서로 근거리 네트워크로 연결되어 있었는데, 이번에 캠퍼스 정보화 사업의 일환으로 모든 건물을 모두 연결하려고 합니다. 모든 건물이 서로 연결되어 있다는 것은 건물 사이의 케이블을 이용해 모든 건물 간에 서로 직접/간접적으로 데이터를 주고받을 수 있다는 것을 의미합니다.

문제를 단순화하기 위해, 모든 건물들은 2차원 평면 위에 있는 점이라고 가정합시다. 두 건물을 직접 연결하려면 두 건물 사이의 거리 만큼의 케이블이 필요합니다. 케이블은 항상 두 건물만을 연결할 수 있으며, 두 케이블이 교차한다고 해서 두 케이블이 직접 연결된 것은 아닙니다.

각 건물들의 위치와 이미 설치된 케이블들에 대한 정보가 주어질 때, 모든 건물을 연결하기 위해 추가로 설치해야 할 케이블 길이의 최소 합을 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 건물의 수 N (N <= 500) 과 이미 설치된 케이블의 수 M (M <= 2000) 이 주어집니다. 각 건물은 0번부터 N-1 번까지의 고유 번호로 구분합니다. 다음 줄에는 N 개의 정수로 0번부터 N-1 번까지 각 건물의 x 좌표가, 그 다음 줄에는 N 개의 정수로 y 좌표가 주어집니다. 각 좌표의 절대값은 1000 이하입니다. 그 후 M 줄에 각 2개의 정수로 각 케이블이 연결하는 두 건물의 번호가 주어집니다. 한 쌍의 건물을 연결하는 케이블이 두 개 이상 있을 수도 있습니다.

출력

각 테스트 케이스마다 한 줄에 추가로 설치해야 할 케이블의 총 길이를 출력합니다. 10-7 이하의 상대/절대 오차가 있는 답도 정답으로 인정합니다.

예제 입력

2
3 1
0 0 1
0 1 2
0 1
10 5
-7 -7 10 -4 10 -4 -5 0 -10 -6
6 8 -5 3 -4 6 -10 4 -7 10
9 7
7 3
9 7
5 0
8 6

예제 출력

1.4142135624 
29.7042202421

노트

3개의 댓글이 있습니다.