시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB170514232.558%

문제

남규 나라의 왕 zych는 도로 정비 계획을 만들고 있다. 남규나라의 도시는 2차원 평면에 존재하며, 각 도시는 (xi,yi)에 위치한다. 새롭게 고속도로를 만들어 모든 도시를 고속도로를 통하여 다른 모든 도시로 이동이 가능하게 만들고자 한다. 고속도로 하나 하나는 다른 도시들을 거치지 않아야 하며, 두 도시를 직선으로 연결하여야 한다. 두 고속도로가 교차한다고 해서 교차로가 생기지 않는다. 이동 가능하다는 것은 한 도시에서 한 개 이상의 고속도로를 통하여 다른 도시를 갈 수 있다는 것을 의미한다. 고속도로는 양방향으로 연결된다.

하지만 고속도로는 길이에 상관없이 한 도로를 만드는데 매우 많은 돈이 들어, 고속도로의 개수 자체를 최대한 적게 만들고자 한다. 그러면서도 수익 측면도 같이 고려하고 있는데, 한 고속도로를 이용하는데 그 도로의 거리 제곱만큼의 비용이 들어간다. 남규 나라의 왕 zych는 수익을 늘리기 위하여 새롭게 만드는 모든 고속도로의 비용의 합을 최대로 하려한다. 각 도로의 거리는 두 도시의 위치를 (x1,y1),(x2,y2) 라고 할 때 sqrt((x1-x2)^2+(y1-y2)^2) 이다.

현재 남규나라에 존재하는 도시와 이미 건설 되어있는 고속도로들의 정보들이 주어졌을 때, 새롭게 만드는 고속도로의 개수를 최소로 하며, 모든 도시에서 다른 도시로 이동 가능하며, 도로의 비용 합을 최대화 하는 도로 정비 계획을 세울 때, 그 도로 비용의 합을 출력하시오.

입력

첫째 줄에는 도시의 개수 n,이미 존재하는 고속도로의 개수 m이 주어진다.(1≤n≤500, 0≤m≤2000)

다음 n줄에는 도시의 좌표 x,y가 주어진다.(-1,000,000≤x,y≤1,000,000) 두 도시가 같은 위치에 존재하지 않는다.

다음 m줄에는 고속도로가 잇는 두 정점 a,b가 주어진다. (1≤a,b≤n)

출력

고속도로의 개수를 최소로 하며, 모든 도시를 다른 도시로 이동 가능하며, 도로의 비용 합을 최대화할 때 그 비용의 합을 출력하시오.

예제 입력 1

3 1
1 1
2 2
3 3
1 2

예제 출력 1

2

예제 입력 2

5 3
1 1
2 3
3 6
6 7
-1 -10
1 2
1 3
2 3

예제 출력 2

610