입자 교환

한 연구팀이 입자물리 실험을 준비한다. 평평한 판 위에 노드 $n$개를 놓고 전선으로 이었다. 전선은 판 위에서 서로 교차할 수 있다.

실험이 시작되면 서로 다른 두 노드에 입자 한 쌍이 나타난다. 보통 물질 입자는 노드 $A$에, 짝이 되는 반물질 입자는 노드 $B$에 나타난다. 목표는 두 입자의 위치를 맞바꾸는 것, 즉 물질 입자가 노드 $B$에 있고 반물질 입자가 노드 $A$에 있는 상태에 도달하는 것이다. 실험은 이동을 여러 번 이어서 진행한다. 한 번의 이동은 두 입자 중 하나를 지금 있는 노드에서 전선으로 이어진 이웃 노드로 보내는 것이다.

물질과 반물질이 너무 가까워지면 서로 소멸하면서 실험 전체가 날아간다. 그래서 연구팀은 위치를 맞바꾸는 동안 두 입자 사이의 유클리드 거리가 가장 작았던 값을 최대한 크게 만들려고 한다. 이 최솟값을 실험의 안전도라고 한다. 입자가 전선을 지나는 중에는 위치를 따지지 않으므로, 위험한 순간은 두 입자가 모두 노드에 있을 때뿐이다.

입자가 어디에 나타날지는 아직 모른다. 물리학자들은 시작 노드 쌍 $(A, B)$의 후보를 $\ell$개 적어 두었고, 후보마다 얻을 수 있는 안전도의 최댓값을 알고 싶다.

첫 줄에 노드의 개수 $n$ ($1 \le n \le 500$)이 주어진다. 다음 $n$개 줄에는 노드 하나의 좌표를 나타내는 두 정수 $x$, $y$ ($-10000 \le x, y \le 10000$)가 1번 노드부터 $n$번 노드까지 순서대로 주어진다. 같은 점에 놓인 노드는 없다.

다음 줄에 전선의 개수 $m$ ($0 \le m \le 2000$)이 주어진다. 다음 $m$개 줄에는 두 정수 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 주어지며, 노드 $a$와 노드 $b$가 전선으로 이어져 있다는 뜻이다. 두 노드를 잇는 전선은 많아야 하나이고, 자기 자신을 잇는 전선은 없다.

다음 줄에 후보 목록의 길이 $\ell$ ($1 \le \ell \le \binom{n}{2}$)이 주어진다. 다음 $\ell$개 줄에는 시작 노드 $A$와 $B$의 번호를 나타내는 두 정수 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 주어진다. 목록에 있는 모든 쌍은 안전도가 양수인 교환이 가능하므로, 두 입자가 같은 노드에 놓일 일은 없다.

$\ell$개 줄을 출력한다. $i$번째 줄에는 목록의 $i$번째 쌍에서 얻을 수 있는 안전도의 최댓값을 소수점 아래 8자리까지, 그 자리에서 가장 가까운 값으로 반올림해 출력한다. 얻을 수 있는 안전도는 항상 두 노드 사이의 거리이므로, 답은 어떤 정수의 제곱근이다.