Life Connections

판도라에서는 모든 나비(Navi)가 친구 관계로 서로 연결되어 있다. 그레이스는 나비들 사이의 친구 관계를 꼼꼼히 조사한 뒤, 두 나비가 얼마나 강하게 연결되어 있는지를 측정하려고 한다. 그녀는 각 나비를 그래프의 정점으로, 각 친구 관계를 무방향 간선으로 나타낸다. 그리고 두 나비 사이의 연결 강도를, 한 나비에서 다른 나비로 갈 수 있는 서로 다른 최단 경로의 개수로 정의한다. 이 값들을 계산하도록 그레이스를 도와주자.

친구 관계 목록과 두 나비 $u$, $v$가 주어질 때, $u$와 $v$ 사이의 서로 다른 최단 경로의 개수를 구하여라. 경로의 길이는 그 경로에 포함된 나비의 수이다. 두 경로는 지나는 나비가 하나라도 다르면 서로 다른 경로로 본다.

친구 관계 목록은 GRAPH BEGIN 이라고 적힌 줄로 시작한다. 그 뒤의 각 줄은 먼저 나비(정점) 하나를 적고, 같은 줄에 그 나비의 친구들(간선)을 나열한다. GRAPH END 라고 적힌 줄이 나오면 친구 관계 목록이 끝난다. 그 다음 줄들에는 연결 강도를 계산해야 할 나비 쌍이 한 줄에 하나씩 주어진다. 이 질의 줄들이 끝난 뒤에는 또 다른 독립적인 인스턴스가 다시 GRAPH BEGIN 부터 이어질 수 있다. 입력이 끝날 때까지 모든 인스턴스를 처리한다.

그래프는 항상 연결되어 있다고 가정해도 된다(모든 나비는 서로 도달할 수 있다). 모든 나비가 자기 줄의 맨 앞에 등장하지는 않는다. 즉, 어떤 나비의 친구 관계는 다른 나비의 줄을 통해서만 암시적으로 주어질 수도 있다.

각 질의에 대해, 입력과 같은 순서로 나비 쌍을 출력하고 그 뒤에 두 나비 사이의 최단 경로 개수를 이어서 한 줄에 출력한다.

예를 들어 나비 a와 e의 연결 강도는 2이다. a에서 e로 가는 가장 짧은 길이 3의 경로가 정확히 두 개(a → b → d → e와 a → c → d → e) 있기 때문이다.