A common word puzzle found in many newspapers and magazines is the word transformation. By taking a starting word and successively altering a single letter to make a new word, one can build a sequence of words which changes the original word to a given end word. For instance, the word ``spice'' can be transformed in four steps to the word ``stock'' according to the following sequence: spice, slice, slick, stick, stock. Each successive word differs from the previous word in only a single character position while the word length remains the same.

Given a dictionary of words from which to make transformations, plus a list of starting and ending words, your team is to write a program to determine the number of steps in the shortest possible transformation.

Input and Output

The first line of the input is an integer N, indicating the number of test set that your correct program should test followed by a blank line. Each test set will have two sections. The first section will be the dictionary of available words with one word per line, terminated by a line containing an asterisk (*) rather than a word. There can be up to 200 words in the dictionary; all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.

Following the dictionary are pairs of words, one pair per line, with the words in the pair separated by a single space. These pairs represent the starting and ending words in a transformation. All pairs are guaranteed to have a transformation using the dictionary given. The starting and ending words will appear in the dictionary.

Two consecutive input set will separated by a blank line.

The output should contain one line per word pair for each test set, and must include the starting word, the ending word, and the number of steps in the shortest possible transformation, separated by single spaces. Two consecutive output set will be separated by a blank line.

Sample Input

1

dip
lip
mad
map
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod

Sample Output

spice stock 4
may pod 3

#include<stdio.h>
#include<string.h>
int main() {
	char s[101], sx[101], sy[101], D[201][20];
	int map[201][201], mt[201], size;
	int n, i, j, k, fx, fy;
	scanf("%d", &n);
	getchar();
	gets(s);
	while(n--) {
		size = 0;
		while(gets(s)) {
			if(s[0] == '*')	break;
			strcpy(D[size], s);
			size++;
		} 
		memset(mt, 0, sizeof(mt));
		for(i = 0; i < size; i++) {
			for(j = 0; j < size; j++) {
				int dif = 0;
				for(k = 0; D[i][k] && D[j][k]; k++)
					if(D[i][k] != D[j][k])
						dif++;
				if(D[i][k] == 0 && D[j][k] == 0 && dif == 1)
					map[i][mt[i]++] = j, map[j][mt[j]++] = i;
			}
		}
		while(gets(s)) {
			if(s[0] == '\0')	break;
			sscanf(s, "%s %s", sx, sy);
			for(i = 0; i < size; i++)
				if(!strcmp(sx, D[i])) {
					fx = i;break;
				}
			for(i = 0; i < size; i++)
				if(!strcmp(sy, D[i])) {
					fy = i;break;
				}
			printf("%s %s ", sx, sy);
			if(fx == fy)	puts("0");
			else {
				int Used[size], Q[size*size], Qt = -1, V[size], tn;
				memset(Used, 0, sizeof(Used));
				Q[++Qt] = fx, V[fx] = 0, Used[fx] = 1;
				for(i = 0; i <= Qt; i++) {
					tn = Q[i];
					if(tn == fy)	break;
					for(j = 0; j < mt[tn]; j++)
						if(Used[map[tn][j]] == 0) {
							Used[map[tn][j]] = 1, V[map[tn][j]] = V[tn]+1;
							Q[++Qt] = map[tn][j];
						}
				}
				printf("%d\n", V[fy]);
			}
		}
		if(n)	puts("");
	}
    return 0;
}