import java.util.*;

public class BFS extends DFS
{

    public static void main(String[] s)
    {
	DFS tee = new DFS(Integer.parseInt(s[2]));
	tee.readFile(s[0]);
	DFS ee = new DFS(Integer.parseInt(s[2]));
	ee.readFile(s[1]);
	LinkedList openList=new LinkedList();
	Vector closedList=new Vector();
	System.out.println(ee.toString());
	for (long i=0; i<10000000; i++)
	    {
		Vector legalM = ee.legalMoves();
		for (Object o : legalM)
		    {
			if (((DFS)o).isSame(tee))
			    {
				System.out.println("GOTIT" + i);
				System.exit(0);
			    }
			if (!inList(o, openList) &&
			    !inList(o, closedList))
			    openList.add(o);
		    }
		if (i % 1000 == 1)
		    System.out.println(i + "  " + openList.size() + "  " + (openList.size()/(i*1.0)));
		ee = (DFS) openList.removeFirst();
		closedList.add(ee);
		//System.out.println(ee.toString() + "\n");
	    }
	
    }


}