3379：Life Connections

On Pandora all Navi are connected by friendships. After carefully mapping friendships between different Navi, Grace wants to measure the strength of the connection between pairs of Navi. She decides the way to calculate this is to treat Navi as nodes in a graph, and friendships between Navi as edges. Then the connection strength between two Navi can be defined as the number different shortest paths each could take to visit the other. Your goal is to help her calculate these values.

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

Connections between Navi are described beginning with the line “GRAPH BEGIN”. Additional lines lists individual Navi (nodes), followed (on the same line) by their friends (edges). The line “GRAPH END” ends the list of connection descriptions. The next lines describe pairs of Navi for which answers need to be calculated, each on a single line. Following these lines, a new instance of the problem can be given, starting from scratch.

You may assume all Navi are connected (i.e., any Navi can reach another Navi by some path). Not all Navi will have their connections listed on a separate line: the friendships of some Navi may only be implied by the friendships given on other lines.

Your output should consist of pairs of Navi in the same order as in the input, followed by the number of shortest paths between them, both on a single line.

For instance, in the following example the strength of the connection between Navi a and e is 2, since there are 2 paths of length 3 (the shortest possible) from a to e (a -> b -> d -> e and a -> c -> d -> e).