소셜 저항 거리

많은 네트워크에서 한 노드가 다른 노드와 얼마나 가까운지 재는 척도가 필요하다. 가장 고전적인 척도는 링크 거리다. 직접 연결된 노드 쌍마다 간선을 놓아 네트워크를 연결 무향 그래프로 나타내면, 두 노드의 링크 거리는 두 노드를 잇는 최단 경로에 놓인 간선의 수다. 배우의 케빈 베이컨 수는 배우를 노드로 두고 같은 영화에 출연한 두 배우를 간선으로 이은 그래프에서 그 배우부터 케빈 베이컨까지의 링크 거리다. 수학자의 에르되시 수는 수학자를 노드로 두고 논문을 함께 낸 두 수학자를 간선으로 이은 그래프에서 폴 에르되시까지의 링크 거리다. 아래 그림의 그래프에서 ALEX와 JORDAN의 링크 거리는 2이고, ALEX와 SAM, ALEX와 DYLAN의 링크 거리는 3이다.

이 그래프에서 JORDAN과 ALEX의 링크 거리, JORDAN과 DYLAN의 링크 거리는 둘 다 2지만, 어떤 의미에서는 JORDAN과 DYLAN이 JORDAN과 ALEX보다 더 가깝게 연결되어 있다. 저항 거리는 그 차이를 거리 값에 반영하려는 시도다. 온라인 소셜 네트워크의 친구 관계에도 같은 생각을 쓴다. 이때 노드는 사람이고, 두 사람의 저항 거리는 그 친분이 얼마나 가까운지를 나타낸다.

두 노드의 저항 거리는 그래프의 모든 간선을 1옴 저항으로 보는 전기 회로에서 두 노드 사이의 저항을 구한 값이다. 노드 $u$를 전압 $V_u$로, 노드 $v$를 전압 $V_v$로 고정하고 ($V_u \ne V_v$) 나머지 노드의 전압은 자유롭게 두면, 저항은 $(V_u - V_v)$를 $u$에서 $v$로 흐르는 전류로 나눈 값이다. 달리 말해 $u$에서 $v$로 흐르는 전류가 1암페어일 때의 $(V_u - V_v)$가 저항이다.

다음을 기억하자.

1. 각 노드에 붙은 간선을 타고 들어오는 전류의 합은 그 노드가 바깥과 주고받는 전류와 같다. 이 값은 $u$에서 $-1$, $v$에서 $1$, 나머지 노드에서 $0$이다.
2. 노드 $a$에서 노드 $b$로 가는 간선의 전압 강하는 그 간선에 흐르는 전류와 그 간선의 저항을 곱한 값이고, 여기서 저항은 1이다.

노드와 간선으로 주어진 그래프와 노드 쌍의 목록을 읽어, 각 쌍의 저항 거리를 구하는 프로그램을 작성하라.

첫째 줄에 데이터 집합의 수 $P$ ($1 \le P \le 10\,000$)가 주어진다. 모든 데이터 집합은 같은 방식으로 서로 독립적으로 처리한다.

각 데이터 집합의 첫 줄에는 데이터 집합 번호 $K$, 노드 수 $N$ ($2 \le N \le 20$), 질의 수 $Q$ ($1 \le Q \le 10$), 간선 수 $E$ ($1 \le E \le N(N-1)/2$)가 주어진다. 데이터 집합 번호는 입력에 나온 순서대로 1부터 매겨진다. 그다음에 간선을 설명하는 줄이 오고, 이어서 저항 거리를 구할 노드 쌍을 나열한 줄이 온다.

간선을 설명하는 줄에는 노드 번호 $n$ ($1 \le n \le N$), 개수 $c$, 그리고 $n$과 간선으로 이어진 노드 $c$개가 주어진다. 이런 줄은 간선이 정확히 $E$개 주어질 때까지 이어진다. 그래프에 자기 루프와 다중 간선은 없고, 그래프는 연결되어 있다.

이어지는 $Q$개의 줄에는 각각 질의 번호 $q$ ($1 \le q \le Q$)와 노드 번호 $n_1$, $n_2$ ($n_1 \ne n_2$)가 주어진다. $n_1$에서 $n_2$까지의 저항 거리를 구해야 한다.

각 데이터 집합마다 한 줄을 출력한다. 그 줄에는 데이터 집합 번호 $K$를 쓰고 공백 하나를 둔 뒤, 입력에 나온 순서대로 저항 거리 $Q$개를 소수점 아래 셋째 자리까지 반올림해 공백 하나로 구분해 출력한다. 소수점 아래 자릿수는 항상 정확히 3개다. 정답이 반올림 경계에 정확히 놓이는 경우는 없다.