uva 429 - Word Transformation.

//Hernández Reyes Jair Said UVa 429 Sol.
// Graph Theory - Simple BFS w/Map.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF (int)(1<<30)
#define MAXN 10000
using namespace std;
map<string, int>mapa;
vector<int>A[MAXN];
ll x, y, z, dx, dy, dist[MAXN];
vector<string> C;
int tryx(string a, string b){
	if ( a.length() != b.length() ) return 0; 
    int cnt = 0;
    for ( int i = 0; i < a.length(); i++ ) {
        if ( a [i] != b [i] ) cnt++;
        if(cnt > 1) return 0;
    }
    return 1;
}
void BFS(ll source){
	queue<int>Q;
	dist[source] = 0;
	Q.push(source);
	while(!Q.empty()){
		ll u = Q.front();Q.pop();
		for(int i = 0; i < A[u].size(); i++){
			int v =  A[u][i];
			if(dist[v] == INF){
				dist[v] = dist[u] + 1;
				Q.push(v);
			}
		}
	}
}
int N;
int main(){
	cin >> N;
	while(N --){
		mapa.clear();
		C.clear();
		string XX, YY;
		int idx = 0;
		for(int i = 0;  i  < MAXN; i++)
			A[i].clear();
		while(cin >> XX){
			if(XX == "*")
				break;
			C.pb(XX);
			if(!mapa[XX]){
				mapa[ XX ] = idx;
				idx++;
			}
		}
		for(int i = 0; i < C.size(); i++)
			for(int j =  0 ; j < C.size(); j++)
				if( tryx(C[i], C[j])  && i != j)
					A[mapa[C[i]]].pb(mapa[C[j]]);
	    string start,to,line;
	    int pos;
	    getline(cin,line);getline(cin,line);
	    while(line != ""){
	      pos = line.find(" ");
	      start = line.substr(0,pos);
	      to = line.substr(pos + 1,line.size());
	      for(int i = 0; i < C.size() + 1; i++)
	      	dist[i] = INF;
	      BFS(mapa[start]);
	      cout << start << " "<<to << " "<<dist[mapa[to]] << endl;
	      if(!getline(cin,line))
	        break;
	    }
	    if(N != 0)
	      cout<<endl;
	}	
	return 0;
}