Life Connections

On Pandora, every Navi is connected to others through friendships. After carefully mapping the friendships among the Navi, Grace wants to measure how strongly any two Navi are connected. She models each Navi as a node of a graph and each friendship as an undirected edge. She then defines the connection strength between two Navi as the number of distinct shortest paths one could take to reach the other. Help her compute these values.

Given the list of friendships and two Navi $u$ and $v$, compute the number of distinct shortest paths between $u$ and $v$. The length of a path is the number of Navi on it. Two paths are different if they pass through at least one different Navi.

The friendship list begins with a line reading GRAPH BEGIN. Each following line first names one Navi (a node) and then, on the same line, lists that Navi's friends (edges). A line reading GRAPH END ends the friendship list. Each line after it holds a pair of Navi whose connection strength must be computed, one pair per line. After these query lines, another independent instance may follow, starting again from GRAPH BEGIN. Process every instance until the input ends.

You may assume the graph is connected (every Navi can reach every other Navi). Not every Navi appears at the start of its own line: some friendships are only implied by the lines given for other Navi.

For each query, print the pair of Navi in the same order as the input, followed by the number of shortest paths between them, all on one line.

For example, the connection strength between Navi a and e is 2, because there are exactly two paths of the shortest length 3 from a to e (a → b → d → e and a → c → d → e).