Desert Travel

You are stranded in a desert. The desert can be viewed as a Cartesian plane. It contains many oases, and you know the $x$- and $y$-coordinates of each one. You will make a series of trips between pairs of oases; each trip has a starting oasis and an ending oasis. On any trip, you may stop at any number of other oases along the way.

Traveling in the desert requires water. Every $1$ unit of distance traveled uses $1$ unit of water. For each trip, you must choose the size of the canteen you will use. You want to use the smallest canteen that can complete the trip, since no one wants to carry more water than necessary.

You can refill the canteen at each oasis along the way so that it lasts until the next oasis. Therefore, the canteen size needed for a trip is the maximum Euclidean distance between consecutive oases on the trip's path. For example, if you travel from $(0,0)$ to $(2,4)$ to $(4,5)$, the maximum distance is about $4.472$, the distance between $(0,0)$ and $(2,4)$, because it is larger than the distance between $(2,4)$ and $(4,5)$. This distance determines the canteen size needed for the trip.

Given the number of oases and several trips, each with a starting oasis and an ending oasis, find for each trip the smallest canteen size needed, that is, the minimum possible maximum Euclidean distance between consecutive oases on a path between the two oases.

The first line contains an integer $O$ ($1 \le O \le 5000$), the number of oases. Each of the next $O$ lines contains two integers; the $i$-th of these lines contains $x_i$ and $y_i$ ($-10^6 \le x_i \le 10^6$ and $-10^6 \le y_i \le 10^6$), the coordinates of the $i$-th oasis. The oases are numbered $1$ through $O$.

The next line contains an integer $Q$ ($1 \le Q \le 500000$), the number of trips. Each of the next $Q$ lines contains two integers; the $i$-th of these lines contains $s_i$ and $e_i$ ($1 \le s_i \le O$ and $1 \le e_i \le O$), the starting and ending oasis numbers for the $i$-th trip.

For each trip, print on a line by itself one number: the smallest canteen size needed for that trip. This is the minimum possible maximum Euclidean distance between consecutive oases on a path from oasis $s_i$ to oasis $e_i$. Answers with absolute or relative error at most $10^{-6}$ are accepted.