package lab11;
import java.util.*;

public class Graph {

	public static void main(String[] args) {
		
		String [][] edges =
		{ 
			 {"Massachusetts","New Hampshire"}, {"New Hampshire","Massachusetts"},
			 {"Massachusetts","New York"}, {"New York","Massachusetts"},
			 {"Massachusetts","Connecticut"}, {"Connecticut","Massachusetts"},
			 {"Massachusetts","Vermont"}, {"Vermont","Massachusetts"},
			 {"Massachusetts","Rhode Island"}, {"Rhode Island","Massachusetts"},
			 {"Connecticut","Rhode Island"}, {"Rhode Island","Connecticut"},
			 {"Connecticut","New York"}, {"New York","Connecticut"},
			 {"Vermont","New York"}, {"New York","Vermont"},
			 {"Vermont","New Hampshire"}, {"New Hampshire","Vermont"},
			 {"Maine","New Hampshire"}, {"New Hampshire","Maine"}	
			
			/*
		      {"YJL087C", "YPL141C"}, {"YPL141C", "YJL087C"},	
			  {"YJL087C", "YIL035C"}, {"YIL035C", "YJL087C"},
			  {"YPL141C", "YJR004C"}, {"YJR004C", "YPL141C"},
			  {"YPL141C", "YPL240C"}, {"YPL240C", "YPL141C"},
			  {"YDL025C", "YDL097C"}, {"YDL097C", "YDL025C"},
			  {"YDL025C", "YPL240C"}, {"YPL240C", "YDL025C"},
			  {"YBL026W", "YDL097C"}, {"YDL097C", "YBL026W"}
			*/
		};
		
		HashSet<String> nodes = new HashSet<String>();
		for( int i = 0; i < edges.length; i++ )
		{
			nodes.add(edges[i][0]);
			nodes.add(edges[i][1]);
		}
		
		HashMap<String, HashSet<String>> graph = new HashMap<String, HashSet<String>>();
		for( int i = 0; i < edges.length; i++ )
		{
			if( graph.get(edges[i][0]) == null )
				graph.put(edges[i][0], new HashSet<String>());
			
			graph.get(edges[i][0]).add(edges[i][1]);
		}
		
		String startNode = "Maine";
		LinkedList<String> queue = new LinkedList<String>();
		HashSet<String> visitedNodes = new HashSet<String>();
		HashMap<String, String> backTrack = new HashMap<String, String>();
		
		queue.addFirst(startNode);
		visitedNodes.add(startNode);
		
		while( !queue.isEmpty() )
		{
			String currentNode = queue.removeLast();
			HashSet<String> neighborSet = graph.get(currentNode);
			Iterator<String> neighbors = neighborSet.iterator();
			while( neighbors.hasNext() )
			{
				String neighborNode = neighbors.next();
				if( !visitedNodes.contains(neighborNode) )
				{
					queue.addFirst(neighborNode);
					visitedNodes.add(neighborNode);
					backTrack.put(neighborNode, currentNode);
				}
			}
		}
		
		Iterator<String> nodes_iterator = nodes.iterator();
		while( nodes_iterator.hasNext() )
		{
			String currentNode = nodes_iterator.next();
			while( currentNode.compareTo(startNode) != 0 )
			{
				System.out.print(currentNode + " -> ");
				currentNode = backTrack.get(currentNode);
			}
			System.out.println(currentNode);
		}
		
	}
}