Social Resistance

Many networks need a measure of how close one node is to another. The classic measure is link distance. Represent the network as a connected undirected graph with an edge between every pair of nodes that have a direct link. The link distance between two nodes is then the number of edges on a shortest path joining them. The Kevin Bacon number of an actor is the link distance from that actor to Kevin Bacon in a graph whose nodes are actors and whose edges join two actors who appeared in the same movie. The Erdos number of a mathematician is the link distance to Paul Erdos in a graph whose nodes are mathematicians and whose edges join two mathematicians who co-authored a published paper. In the graph drawn below, the link distance from ALEX to JORDAN is 2, and the link distance from ALEX to SAM and from ALEX to DYLAN is 3.

In that graph the link distance from JORDAN to ALEX and the link distance from JORDAN to DYLAN are both 2, but in some sense JORDAN and DYLAN are more connected than JORDAN and ALEX. Resistance distance is an attempt to reflect that difference in a distance measurement. The same idea applies to friendships in an online social network. There the nodes are people, and the resistance distance between two of them says how close the friendship is.

The resistance distance between two nodes is the resistance between them when the graph is read as an electrical network with a 1 ohm resistor on every edge. Hold node $u$ at voltage $V_u$ and node $v$ at voltage $V_v$ with $V_u \ne V_v$, and let the voltage at every other node float. The resistance is $(V_u - V_v)$ divided by the current flowing from $u$ to $v$. Put another way, the resistance is $(V_u - V_v)$ when the current from $u$ to $v$ is one ampere.

Recall:

1. At every node, the currents on the edges into that node sum to the current the node exchanges with the outside world. That value is $-1$ at $u$, $1$ at $v$, and $0$ at every other node.
2. The voltage drop across an edge from node $a$ to node $b$ is the current in that edge times the resistance of that edge, which is 1 here.

Write a program that reads a graph given as nodes and edges together with a list of node pairs, and computes the resistance distance for each pair.

The first line contains one integer $P$ ($1 \le P \le 10\,000$), the number of datasets. Process every dataset in the same way and independently of the others.

The first line of each dataset contains the dataset number $K$, the number of nodes $N$ ($2 \le N \le 20$), the number of queries $Q$ ($1 \le Q \le 10$), and the number of edges $E$ ($1 \le E \le N(N-1)/2$). Dataset numbers run from 1 in input order. Lines describing the edges follow, then lines listing the node pairs whose resistance distance you must compute.

Each edge line contains a node number $n$ ($1 \le n \le N$), a count $c$, and the $c$ nodes joined to $n$ by an edge. Edge lines continue until exactly $E$ edges have been given. The graph has no self loop and no parallel edge, and the graph is connected.

Each of the next $Q$ lines contains a query number $q$ ($1 \le q \le Q$) and two node numbers $n_1$ and $n_2$ ($n_1 \ne n_2$). Find the resistance distance from $n_1$ to $n_2$.

Print one line for each dataset. The line contains the dataset number $K$, then a single space, then the $Q$ resistance distances in input order, each rounded to 3 decimal places and separated by single spaces. Always print exactly three digits after the decimal point. No answer sits exactly on a rounding boundary.