Particle Swapping

A research team is preparing an experiment in particle physics. On a flat plate they have built a system of $n$ nodes joined by wires. The wires may cross each other on the plate.

When the experiment starts, a pair of particles appears at two different nodes. One ordinary matter particle appears at node $A$, and the matching antimatter particle appears at node $B$. The goal is to swap the two particles, that is, to reach the state where the matter particle is at node $B$ and the antiparticle is at node $A$. The experiment runs as a sequence of moves. One move sends one of the two particles from the node it occupies to a neighbouring node along a wire.

Matter and antimatter annihilate when they get too close, which destroys the whole experiment. The team therefore wants a swap in which the smallest Euclidean distance between the two particles is as large as possible. That smallest distance is the safeness of the experiment. While a particle travels along a wire its position does not count, so the only risky moments are the moments when both particles are at nodes.

The physicists do not know yet where the particles will appear. They have written down $\ell$ candidate pairs of starting nodes $(A, B)$, and for each candidate they want the largest safeness they can achieve.

The first line contains an integer $n$ ($1 \le n \le 500$), the number of nodes. Each of the next $n$ lines contains two integers $x$ and $y$ ($-10000 \le x, y \le 10000$), the coordinates of one node on the plate, given in order from node 1 to node $n$. No two nodes are at the same point.

The next line contains an integer $m$ ($0 \le m \le 2000$), the number of wires. Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), meaning that a wire joins node $a$ and node $b$. At most one wire joins any two nodes, and no wire joins a node to itself.

The next line contains an integer $\ell$ ($1 \le \ell \le \binom{n}{2}$), the length of the candidate list. Each of the next $\ell$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), the indices of the starting nodes $A$ and $B$. Every listed pair admits a swap with positive safeness, so the two particles never have to occupy the same node.

Print $\ell$ lines. Line $i$ holds the largest safeness achievable for the $i$-th pair on the list, written with exactly 8 digits after the decimal point and rounded to the nearest value at that precision. Every achievable safeness is the distance between two nodes, so each answer is the square root of an integer.