In the year 59451 of the Galactic Calendar, there are many star systems colonized by humans. To travel between star systems, people generally use jump gates that connect two star systems. A jump gate can transmit matter between the two star systems it connects.

Lulu, Huahua, and Xuantuan have been appointed by the Interstellar Alliance Investigation Bureau to investigate the improper business practices of the business giant ZeusLeague+.

There are $N$ star systems in the galaxy that have been successfully entered by ZeusLeague+, labeled $1, 2, \dots, N$. ZeusLeague+ owns $M$ jump gates between these $N$ star systems. Using these jump gates, ZeusLeague+’s supplies can be transmitted between any two of these $N$ star systems. Due to budget constraints, the number of jump gates does not exceed the number of star systems.

After much effort, Lulu obtained the total trade volume $C[i]$ for each of these $N$ star systems.

Xuantuan designed an economic characteristic index $D[i]$ to measure the economic characteristics of these $N$ star systems. Thus, we can use the tuple $(C[i], D[i])$ to represent the XP (Xuan's Position) of the $i$-th star system. Now, suppose we have the XPs of $k$ star systems, place them on a two-dimensional plane, and fit these XPs with a straight line. The repulsion of a straight line with respect to the XPs is defined as the sum of the squares of the Euclidean distances from this line to each XP. Let the linear hypothesis repulsion of the XPs be the minimum of the repulsions of all possible straight lines with respect to the XPs. The smaller this value, the more suspicious the mutual trade activities of ZeusLeague+ in these $k$ star systems, and thus it is worth further investigation. Huahua is responsible for calculating the "non-suspicion degree" for many pairs of star systems $(u, v)$. The non-suspicion degree of a jump gate route is defined as the linear hypothesis repulsion of the XPs of all star systems it passes through (including the start and end points). The non-suspicion degree of a star system pair $(u, v)$ is defined as the minimum of the non-suspicion degrees of all jump gate routes starting at $u$ and ending at $v$. A jump gate route is a process that starts from a certain star system, reaches certain star systems in sequence through jump gates, and then terminates, without passing through the same star system twice.

After days of working day and night, you, the famous computer scientist Hcceleration.Gerk.Gounce from the parallel investigation team, could not bear to see her working without rest, so you decided to help her after finishing your own work.

Input

The first line contains two integers $N$ and $M$, representing the number of star systems and the number of jump gates in the galaxy, respectively.

The next $N$ lines each contain two positive integers $C[i]$ and $D[i]$, representing the XP (Xuan's Position) of the $i$-th star system.

The next $M$ lines describe the jump gates, each containing two positive integers $u[i]$ and $v[i]$, representing a jump gate connecting star systems $u[i]$ and $v[i]$. Note that this connection is undirected. There are no cases where a star system connects to itself, nor are there duplicate connections.

The next line contains a positive integer $Q$, representing the number of star system pairs for which Huahua needs to calculate the non-suspicion degree.

The next $Q$ lines each contain two positive integers $s[i]$ and $t[i]$, representing the pair for which Huahua needs to calculate the non-suspicion degree from $s[i]$ to $t[i]$.

Output

Output $Q$ lines, each containing a real number representing the answer for the $i$-th calculation. Your answer must be within $0.01$ of the standard answer to receive points.

Constraints

Hint: We abstract star systems as points and jump gates as edges. The problem describes a connected undirected graph where the number of edges does not exceed the number of points.

For 100% of the data, $C[i]$ and $D[i]$ are integers in the range $[0, 97]$.

Examples

Input 1

6 6 
3 4 
5 6 
1 3 
4 4 
3 3 
2 4 
1 2 
1 3 
2 3 
2 4 
3 5 
5 6 
3 
3 6 
2 4 
4 6

Output 1

0.66667 
0.00000 
1.67544