E.g. consider the words trend and triad. The Hamming distance is 2 and there is a path of length 2 as well: trend,tread,triad. On the other hand, consider a shortest path (of length 10) from there to which: there, where, whore, whorl, whirl, whirs, whips, whipt, whist, whish, which.
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
aaaac
ccccd
cccce
aaabb
1 3
1 4
5 4
1 6
0 0
Sample Output
1
Not connected
1
2