Code: Select all
import java.util.*;
import java.io.*;
class Main
{
static TreeMap<String, Integer> map;
static Vector<Vector<Integer>> vect;
static int[] dist;
static Vector<String> names;
static Queue<Integer> q;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuffer str = new StringBuffer();
String line = br.readLine();
line = br.readLine();
line = br.readLine();
while(line != null)
{
names = new Vector<String>();
map = new TreeMap<String, Integer>();
line = br.readLine();
int c = 0;
while(!line.equals("*"))
{
names.add(line);
map.put(line, c);
c++;
line = br.readLine();
}
int n = map.size();
vect = new Vector<Vector<Integer>>(n);
for(int j = 0; j < n; j++)
{
Vector<Integer> v = new Vector<Integer>();
vect.add(v);
}
for(int j = 0; j < n; j++)
{
for(int k = j+1; k < n; k++)
{
String s1 = names.get(j);
String s2 = names.get(k);
int d = dist(s1,s2);
if(d == 1)
{
vect.get(map.get(s1)).add(map.get(s2));
vect.get(map.get(s2)).add(map.get(s1));
}
}
}
String[] total = br.readLine().split(" ");
int src;
int d;
while(true)
{
src = map.get(total[0]);
d = map.get(total[1]);
dist = new int[n];
Arrays.fill(dist, -1);
dist[src] = 0;
q = new LinkedList<Integer>();
q.add(src);
boolean check = false;
while(!q.isEmpty())
{
int v = q.poll();
Iterator it = vect.get(v).iterator();
while(it.hasNext())
{
int u = (int)it.next();
if(dist[u] == -1 && u == d)
{
dist[u] = dist[v] + 1;
check = true;
break;
}
else if(dist[u] == -1)
{
dist[u] = dist[v] + 1;
q.add(u);
}
}
if(check)
break;
}
str.append(total[0] + " " + total[1] + " " + dist[d] + "\n");
line = br.readLine();
if(line == null)
break;
else if(line.length() == 0)
break;
else
total = line.split(" ");
}
str.append("\n");
if(line == null)
break;
}
str.deleteCharAt(str.length()-1);
out.write(str.toString());
out.flush();
}
public static int dist(String s1, String s2)
{
if(s1.length() != s2.length())
return -1;
else
{
int d = 0;
for(int i = 0; i < s1.length(); i++)
{
if(s1.charAt(i) != s2.charAt(i))
{
d++;
}
}
return d;
}
}
}
