import java.util.*;
import java.io.*;

public class playLadders {

	private static BufferedReader stdin = new BufferedReader( new InputStreamReader( System.in ) );

	public static boolean differentByOne( String a, String b )
	{
		int diffCount = 0;

		// make sure the two strings are both 5 letters long
		if( a.length() != 5 || b.length() != 5 )
			return false;

		// check the letters of the strings
		for( int i = 0; i < a.length(); i++ )
		{
			if( a.charAt(i) != b.charAt(i) )
			if( ++diffCount > 1 )
				return false;
		}

		return (diffCount == 1);
	}
	

	public static void main(String[] args) {

		String[] wordList = new String[5800];
		myListGraph mg = new myListGraph();

		int counter = 0;
		try
		{
			// This is one way to read from a file. The list of all 5-letter words
			// is in a file called words.dat
			BufferedReader in = new BufferedReader(new FileReader("words.dat"));
			String word;

        		// read all the words from the file                
			System.out.println( "Reading words.dat..." );
			while( (word = in.readLine()) != null )
			{
				// make a new vertex w/ this word
				mg.addVertex(word);

				// see what words it's one letter different from
				for( int i = 0; i < counter; i++ )
					if( differentByOne(word, wordList[i]))
						mg.addEdge( word, wordList[i]);

				wordList[counter++] = word;
			}
			in.close();
		}
		catch (IOException e) {}
		System.out.println("Done constructing the graph....");
		
		try{
		
			System.out.println("Enter the first five-letter word for the Ladders game (0 to quit):  ");
			String word1 = stdin.readLine();
			
			System.out.println("Enter the second five-letter word for the Ladders game (0 to quit):  ");
			String word2 = stdin.readLine();

			// Find shortest path
			String[] path = mg.shortestPath(word1, word2);

			// Check if shortest path really exists
			if(path == null)
			{
				System.out.println("There is no path between " + word1 + " and " + word2);
				return;
			}

			// If not, output shortest path
			System.out.println("Shortest path");
			for(int i = 0; i < path.length; i++)	
				System.out.println(path[i]);	
		
			
		} // end of try
		catch (IOException e) {}
		

	} // end of main method

} // end of class