Hide

Problem F
Social Resistance

In many networks, we need a measure of the closeness of one node to another. The classic measure is link distance. If the network is represented as a connected undirected graph with an edge between any pair of nodes that have a direct link, the link distance is the number of edges in the shortest path between the nodes. For example, the Kevin Bacon number of an actor is the link distance from the actor to Kevin Bacon in a graph with nodes actors and an edge between two actors if they have appeared in the same movie. The Erdős number for mathematicians is the link distance from a mathematician to Paul Erdős in a graph with nodes mathematicians and an edge between two mathematicians if they have co-authored a published paper. In the graph below, the link distance from ALEX to JORDAN is $2$ and the link distance from ALEX to SAM or DYLAN is $3$.

\includegraphics[width=.5\textwidth ]{social.png}

In the graph, the link distance from JORDAN to ALEX or to DYLAN is the same ($2$) but JORDAN and DYLAN are in some sense “more connected” than JORDAN and ALEX. An attempt to reflect this in a distance measurement is resistance distance. This is similar to the relationship between friends in online social networks. In this case, the nodes in the graph are people (as shown above) and the resistance distance between them is the closeness of their friendship.

The resistance distance between two nodes in a graph is computed by finding the resistance between the two nodes in the graph as an electrical network with $1$ Ohm resistors for each edge. That is: if node $1$ is held at $V_1$ and node $2$ is held at $V_2$, ($V_2 \ne V_1$), and the voltages at all other nodes are allowed to float, the resistance is ($V_1 - V_2$) / (current from node $1$ to node $2$). Or, the resistance is ($V_1 - V_2$) when the current from node $1$ to node $2$ is one Ampere.

Recall:

  1. The sum of the currents on edges into a node must be the current flowing out to the external world ($-1$ for node $1$, $1$ for node $2$ and $0$ for all other nodes).

  2. The voltage drop across an edge from node $a$ to node $b$ is the current in the edge times the resistance along the edge (which is $1$ in our case).

For this problem, you will write a program which takes as input the description of a graph as nodes and edges and a list of pairs of nodes in the graph and computes the resistance distance between each pair of nodes in the list. The sample Input/Output below computes the resistance distance from node JORDAN to each other node in the picture above.

Input

Input consists of a single data set which consists of multiple lines of input. The first line contains 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 \frac{N \cdot (N-1)}{2}$). This line is followed by a set of lines describing the edges and then a set of lines giving a list of resistance distances to compute for the graph.

The edges are described by a sequence of lines containing a node number, $n$ ($1 \le n \le N$), a count and the nodes which are connected to node $n$. The sequence ends when $E$ edges have been specified. There will be no self-loops or parallel edges.

The queries are described by $Q$ lines, each of which has a query number, $q$ ($1 \le q \le Q$), and two node numbers $n_1$ and $n_2$. The program is to find the resistance distance from $n_1$ to $n_2$. The query number starts at $1$ and increments by $1$ for each query.

Output

For each query, output the queried resistance distance on a single line. Your answer will be considered correct if its relative or absolute error is less than $10^{-3}$.

Sample Input 1 Sample Output 1
6 5 8
3 3 1 2 4
4 3 2 5 6
5 2 2 6
1 2 1
2 2 3
3 2 4
4 2 5
5 2 6
1.619048
0.619048
0.476190
0.571429
0.904762

Please log in to submit a solution to this problem

Log in