Description

In Galactic Year $59451$, there are many star systems in the Milky Way that have been colonized by humans. To travel between planetary systems, people typically use jump gates that connect two planetary systems. A jump gate can transfer matter between the two planetary systems it connects. Lulu, Huahua, and Xuānxuān are appointed by the Galactic Interstellar Alliance Investigation Bureau to investigate the unfair business practices of the commercial giant ZeusLeague+.

There are $N$ planetary systems where ZeusLeague+ has successfully entered the market, labeled $1, 2, \ldots, N$. ZeusLeague+ also owns $M$ jump gates among these $N$ planetary systems. Using these jump gates, ZeusLeague+ can transport goods between any pair of the $N$ planetary systems. Due to budget constraints, the number of jump gates does not exceed the number of planetary systems.

After considerable effort, Lulu obtained the total trade volume $C_i$ of ZeusLeague+ in each of the $N$ planetary systems.

Xuānxuān designed an economic characteristic index $D_i$ to measure the economic features of these $N$ planetary systems. Thus, we can use the pair $(C_i, D_i)$ to denote the XP (Xuan's Position) of the $i$-th planetary system. Now suppose we have the XPs of $k$ planetary systems and place them on a 2D plane. We then fit a straight line to these XPs. Define the repulsiveness of a straight line with respect to the XPs as the sum of squared Euclidean distances from that line to each XP. Then define the linear-hypothesis repulsiveness of the XPs as the minimum repulsiveness over all straight lines. The smaller this value is, the more suspicious the mutual trade activities of ZeusLeague+ among these $k$ planetary systems are, and thus more deserving of further investigation.

Huahua is responsible for computing the non-suspiciousness of many pairs of planetary systems $(u, v)$. The non-suspiciousness of a jump-gate route is defined as the linear-hypothesis repulsiveness of the XPs of all planetary systems it passes through (including the start and end). The non-suspiciousness of a pair of planetary systems $(u, v)$ is defined as the minimum, over all jump-gate routes starting at $u$ and ending at $v$, of the non-suspiciousness of those routes. A jump-gate route is a process that starts from some planetary system, visits some planetary systems in sequence via jump gates, and then terminates, without visiting any planetary system more than once.

After days and nights of work by Huahua, you—the renowned computer scientist Hcceleration.Gerk.Gounce from the parallel investigation team—cannot bear to see her working without rest. Having completed your own tasks, you decide to help her.

Input Format

The first line contains $N, M$, the number of planetary systems in the galaxy and the number of jump gates, respectively. The next $N$ lines each contain two positive integers $C_i, D_i$, representing the XP (Xuan's Position) of the $i$-th planetary system. The next $M$ lines describe the jump gates, each with two positive integers $u_i, v_i$, indicating there is a jump gate connecting planetary systems $u_i$ and $v_i$. Note that this connection is undirected. There are no self-loops and no multiple edges. The next line contains a positive integer $Q$, the number of pairs of planetary systems for which Huahua needs to compute the non-suspiciousness. The following $Q$ lines each contain two positive integers $s_i, t_i$, indicating that Huahua needs to compute the non-suspiciousness from $s_i$ to $t_i$.

Output Format

Output $Q$ lines. Each line contains a real number, which is the answer to Huahua’s $i$-th query. Your answer must differ from the standard answer by no more than $0.01$ to receive credit.

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

0.66667 
0.00000 
1.67544

Hint

$1\leq N, M, Q\leq 10^5, 1\leq u_i, v_i, s_i, t_i\leq N, 1\leq C_i, D_i\leq 100.$

Brief statement (by yummy): In a simple, unweighted, undirected, connected graph with the number of edges not exceeding the number of nodes, each node corresponds to a coordinate in the Cartesian plane. There are $Q$ queries. For each given pair of nodes, find a path and a straight line such that the sum of squared distances from the coordinates of nodes on that path to the line is minimized, and output the minimum value.

[spj 0.01]

Translated by ChatGPT 5