Problem F
Particle Swapping

From flickr under Creative Commons licence, by Tom Fassbender

The research team of prof. Feynmansson is preparing a new groundbreaking experiment in particle physics. On a special plate they have prepared a system consisting of a number of nodes connected via wires¹. In the beginning of the experiment a pair of particles appears at two different nodes of the system: one normal particle of matter appears at some node $A$, and one corresponding particle of antimatter appears at some node $B$. The goal of the experiment is to swap these particles, i.e., to arrive at a state where the normal particle is at node $B$ and the antiparticle is at node $A$. This state should be reached by a sequence of moves, where each move consists of transmitting one of the particles from its current location to a neighbouring node via a wire.

As you probably remember from popular science TV programmes, playing with matter and antimatter is usually not that safe. In particular, if particles of matter and antimatter get too close to each other, they will annihilate each other blowing up the whole experiment. Therefore, the research team would like to swap the locations of the particles in such a manner that the minimum Euclidean distance between them during the experiment is as large as possible. This minimum distance is called the safeness of the experiment. For simplicity, we assume that while a particle is transmitted via a wire we do not consider its location; in other words, the only risky moments during the experiment are when both particles are at some nodes. You may assume that it is always possible to swap the particles with positive safeness, that is, so that the particles are never placed at the same node during swapping.

Another catch is that the physicists do not know precisely where the particles will appear. They have made a list of potential pairs of initial locations $(A,B)$, and for each of them they would like to know the maximum possible safeness of swapping the particles. Help them in this task.

Input

The first line of the input contains a single integer $n$ ($1\leq n\leq 500$), denoting the number of nodes in the system. Then follow $n$ lines, each containing two integers $x,y$ ($-10\ 000\leq x,y\leq 10\ 000$); the numbers in the $i$-th line denote the coordinates on the plate of the $i$-th node. No two nodes are located at the same point.

The next line of the input contains a single integer $m$ ($0\leq m\leq 2\ 000$), denoting the number of wires in the system. Then follow $m$ lines; each line contains a description of a wire as a pair of integers $a,b$ ($1\leq a,b\leq n$, $a\neq b$), denoting the indices of the nodes that are connected by the wire. You may assume that no two nodes are connected by more than one wire, and no wire connects a node with itself.

The next line of the input contains a single integer $\ell $ ($1\leq \ell \leq \binom {n}{2}$), denoting the length of the list of potential initial positions prepared by the physicists. Then follow $\ell $ lines, each containing two integers $a,b$ ($1\leq a,b\leq n$, $a\neq b$), denoting the indices of the initial nodes $A$ and $B$, respectively.

Output

Output exactly $\ell $ lines. The $i$-th line of the output should contain a single floating point number, being the maximum possible safeness for the $i$-th pair of initial positions listed by the physicists. Absolute or relative errors of value at most $10^{-6}$ will be tolerated.

6
0 0
-1 3
-1 0
-1 -3
3 0
0 1
6
1 2
2 3
3 4
4 1
1 5
5 6
5
6 5
2 4
2 6
3 6
4 6

1.00000000
3.16227766
2.23606798
1.41421356
3.16227766