We can then study shortest paths in this weighted graph. For example, given two words, what is the shortest path between them (shortest here means "least cost")?
In this question you will be given an English dictionary with all 5 letter words, one word per line, but not in lexicographic order. Then you will be given a set of node pairs, each with 2 numbers and you will print the shortest distances between those node pairs.
Input
The first line of input contains a single integer n (n < 6000). Each of the next n lines contains a five letter word. Considering these numbered as 1..n, the next few lines each contain a pair of node numbers i, j (both i,j are between 1 and n, inclusive) The last line of input contains the pair 0 0. Do not process this line.
Output
For each pair i,j, (other than the 0 0 in the last line), print out the shortest path length between nodes i,j in the graph you created. If there is no path, print the string "Not connected".
Sample Input
6
aaaaa
aaaab
aaaba
ccccd
cccce
aaabb
1 6
2 3
1 4
0 0
Sample Output
2
2
Not connected