고속도로

섬나라 플라토피아(Flatopia)는 완벽하게 평평하지만 공공 고속도로망이 빈약하다. 정부는 이미 일부 도시를 잇는 고속도로 몇 개를 건설했지만, 아직 고속도로로 갈 수 없는 도시가 남아 있다. 모든 도시 쌍 사이를 고속도로만으로 오갈 수 있도록 고속도로를 더 건설해야 한다.

도시는 $1$번부터 $N$번까지 번호가 매겨져 있으며, $i$번 도시는 좌표 $(x_i, y_i)$에 있다. 각 고속도로는 정확히 두 도시를 직선으로 잇고 양방향으로 통행할 수 있으며, 그 길이는 두 도시 사이의 유클리드 거리와 같다. 고속도로끼리 교차할 수는 있지만, 운전자는 두 고속도로가 모두 끝나는 도시에서만 서로 갈아탈 수 있다.

정부는 가능한 한 적은 비용으로 모든 도시를 서로 연결하려 한다. 땅이 평평하므로 고속도로의 비용은 길이에 비례하고, 따라서 가장 저렴한 방법은 새로 건설하는 고속도로 전체의 길이를 최소화하는 것이다.

첫째 줄에 도시의 수 $N$ ($1 \le N \le 750$)이 주어진다.

다음 $N$개의 줄에는 각각 두 정수 $x_i$와 $y_i$ ($|x_i|, |y_i| \le 10000$)가 주어지며, 이는 $i$번 도시의 좌표이다($i$는 $1$부터 $N$까지). 모든 도시의 위치는 서로 다르다.

그다음 줄에는 이미 건설된 고속도로의 수 $M$ ($0 \le M \le 1000$)이 주어진다. 이어지는 $M$개의 줄에는 각각 이미 직접 연결된 서로 다른 두 도시의 번호가 주어진다. 어떤 두 도시 사이에도 이미 건설된 고속도로는 최대 한 개다.

기존 고속도로와 새 고속도로를 함께 사용하여 모든 도시가 서로 연결되도록, 새로 건설하는 고속도로 전체의 길이를 최소로 하여 고속도로를 건설한다.

이때 최소 전체 길이는 유클리드 거리(제곱근)의 합이므로, 정수로 나타내기 위해 새로 건설하는 고속도로들의 길이의 제곱의 합을 출력한다. 즉, 전체 길이가 최소인 방법에서 $i$번과 $j$번 도시를 잇는 새 고속도로마다 $(x_i - x_j)^2 + (y_i - y_j)^2$을 더한 값을 정수 하나로 출력한다.

전체 길이가 최소인 방법이 여러 개 있어도 이 값은 유일하게 결정된다. 이미 모든 도시가 연결되어 새 고속도로가 필요 없다면 $0$을 출력한다.