Resistor Network Voltage Computation

You are given an electrical resistor network. Each edge in the network represents a resistor with a given resistance. In addition, the voltage (with respect to the negative terminal) is provided for some nodes. The power supply voltage is constant. Your task is to compute the voltage difference (absolute value) between any two queried nodes.

Problem Details

The network is represented as an undirected graph with N nodes and M edges. Each edge contains the two endpoints and its resistance. Then, K nodes have their voltage set to a specified value. The remaining nodes have unknown potentials and must be determined using Kirchhoff’s current law (KCL). For each node with unknown potential, the sum of currents (voltage differences divided by resistance) flowing out of it is zero.

For an unknown node i, if it is connected to a node j with an edge resistance r, then the contribution is \(\frac{1}{r}\). If node j has a fixed voltage, its contribution is moved to the right-hand side of the equation; otherwise, it becomes part of the coefficient matrix. The resulting system of linear equations can be solved using Gaussian elimination.

Once the potentials for all nodes are determined, you need to answer Q queries. Each query asks for the voltage difference between two nodes, which is the absolute difference between their voltages.

Note: All formulas are represented in \(\LaTeX\) format. For example, the current balance equation for an unknown node \(i\) is given by:

[ \left( \sum_{j:, (i,j) \in E} \frac{1}{r_{ij}} \right) V_i - \sum_{j:, (i,j) \in E,, \text{unknown}} \frac{1}{r_{ij}} V_j = \sum_{j:, (i,j) \in E,, \text{fixed}} \frac{1}{r_{ij}} V_j. ]

inputFormat

The input is given as follows:

1. The first line contains two integers \(N\) and \(M\) representing the number of nodes and the number of edges in the resistor network.
2. The next \(M\) lines each contain three numbers \(u\), \(v\) and \(r\) where \(u\) and \(v\) are the endpoints of an edge and \(r\) is the resistance on that edge.
3. The next line contains an integer \(K\) indicating the number of nodes with a known voltage.
4. The following \(K\) lines each contain a node index and its voltage value (a floating-point number).
5. The next line contains an integer \(Q\) representing the number of queries.
6. The next \(Q\) lines each contain two integers \(a\) and \(b\), representing a query asking for the voltage difference between node \(a\) and node \(b\).

Nodes are numbered from 1 to \(N\). It is guaranteed that all values are provided and that there are more than 2 test cases in the judging data.

outputFormat

For each query, output a single line containing the absolute difference between the two nodes' voltages. The result should be printed with exactly two decimal places.

sample

3 3
1 2 1
2 3 2
1 3 3
1
1 10.0
2
2 3
1 3

0.00
0.00