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"}	
			
		};
		
		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";
		String endNode = "Rhode Island";
		
		
		LinkedList<String> queue = new LinkedList<String>();
		HashSet<String> visited = new HashSet<String>();
		HashMap<String, String> parents = new HashMap<String, String>();
		
		queue.add(startNode);
		visited.add(startNode);
		
		while( !queue.isEmpty()){
			String node = queue.remove();
			for(String neighbor : graph.get(node)){
				if(!visited.contains(neighbor)){
					queue.add(neighbor);
					visited.add(neighbor);
					parents.put(neighbor, node);
				}
			}
		}
		
		Vector<String> path = new Vector<String>();
		String node = endNode;
		while(node != null){
			path.add(node);
			node = parents.get(node);
		}
		for(int x = path.size() - 1; x >= 0; x--){
			System.out.print(path.get(x));
			if(x > 0)
				System.out.print("->");
		}
	}
}