Galaxy XP Non-suspiciousness

In the Galaxy Calendar \(59451\), many star systems have been colonized by humans throughout the galaxy. In order to travel between star systems, interstellar jump gates are used. Each jump gate connects exactly two star systems and enables bidirectional transport. ZeusLeague+ has installed its own jump gates among \(N\) star systems, labeled \(1, 2, \ldots, N\), and using these gates, material can be transferred between any two of them. It is guaranteed that the number of jump gates \(M\) does not exceed \(N\).

For each star system \(i\), two economic indicators are given: a trade volume \(C_i\) and an economics characteristic \(D_i\). We refer to the pair \((C_i, D_i)\) as the XP (Xuan's Position) of star system \(i\). Consider any set of \(k\) star systems and their corresponding XPs, which are points in the plane. For any line in the plane, define its repulsion degree with respect to these XPs as the sum of the squared Euclidean distances from each XP to the line. The linear hypothesis repulsion degree of these \(k\) XPs is the minimum repulsion degree over all lines. In other words, if the points are very well aligned (i.e. almost collinear), the minimal sum will be small, making the trade among these star systems more suspicious.

For a given jump route — a simple path (i.e. no repeated star systems) in the star system network obtained by consecutively traversing jump gates — its non-suspiciousness is defined as the linear hypothesis repulsion degree of the set of star systems (their XPs) in that route. For a pair of star systems \((u,v)\), its non-suspiciousness value is the minimum non-suspiciousness among all jump routes starting at \(u\) and ending at \(v\>.

Your task is to help compute this value. You are given a connected network of \(N\) star systems and \(M\) bidirectional jump gates. In addition, you are given the values \(C_i\) and \(D_i\) for \(i=1,2,\ldots,N\). Then there are \(Q\) queries. Each query consists of two star system indices \(u\) and \(v\). For each query, compute the minimum non-suspiciousness value among all simple paths from \(u\) to \(v\>.

Note on computing the linear hypothesis repulsion degree:

Given a set of \(k\ge2\) points \((x_i,y_i)\) for \(i=1,2,\ldots, k\), let \[ \bar{x} = \frac{1}{k}\sum_{i=1}^k x_i,\quad \bar{y} = \frac{1}{k}\sum_{i=1}^k y_i. \] Define \[ S_{xx} = \sum_{i=1}^k (x_i-\bar{x})^2,\quad S_{yy} = \sum_{i=1}^k (y_i-\bar{y})^2,\quad S_{xy} = \sum_{i=1}^k (x_i-\bar{x})(y_i-\bar{y}). \] Then the minimal sum of squared distances to a line is: \[ D = \frac{1}{2} \Bigl[(S_{xx}+S_{yy}) - \sqrt{(S_{xx}-S_{yy})^2+4S_{xy}^2}\Bigr]. \] For a single point (\(k=1\)), define \(D=0\).

Input Format:

• The first line contains three integers \(N, M, Q\): the number of star systems, jump gates, and queries respectively.
• The second line contains \(N\) integers \(C_1, C_2, \ldots, C_N\) representing the trade volumes.
• The third line contains \(N\) integers \(D_1, D_2, \ldots, D_N\) representing the economic characteristics.
• The next \(M\) lines each contain two integers \(u\) and \(v\), indicating that there is a bidirectional jump gate between star systems \(u\) and \(v\).
• The next \(Q\) lines each contain two integers \(u\) and \(v\), representing a query asking for the minimum non-suspiciousness value from \(u\) to \(v\).

Output Format:

• For each query, output the minimum non-suspiciousness value. Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

inputFormat

The input begins with a line containing three integers \(N, M, Q\). The next line contains \(N\) space-separated integers denoting \(C_i\) for \(i=1,2,\ldots,N\). The following line contains \(N\) space-separated integers denoting \(D_i\). Each of the next \(M\) lines contains two space-separated integers \(u\) and \(v\), indicating a bidirectional jump gate between star systems \(u\) and \(v\). Finally, there are \(Q\) lines, each with two integers \(u\) and \(v\), representing a query.

outputFormat

For each query, output a single line containing the minimum non-suspiciousness value (a floating point number) for a simple path from \(u\) to \(v\). Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

sample

3 2 2
1 2 3
1 2 3
1 2
2 3
1 3
1 2

0.000000
0.000000