import java.util.*;

import us.jubat.graph.*;

public class Search {
	public static final String HOST = "127.0.0.1";
	public static final int PORT = 9199;
	public static final String instance_name="";
	
	public static Map<String,String> station_map = new HashMap<String, String>();
	
	public static void search_route(String f_id, String t_id)throws Exception {
		GraphClient client = new GraphClient(HOST, PORT, instance_name, 10);
		PresetQuery pq = new PresetQuery();
		ShortestPathQuery spreq = new ShortestPathQuery(f_id, t_id, 100, pq);
		List<String> stations = new ArrayList<String>(client.getShortestPath(spreq));
		
		System.out.println("Pseudo-Shortest Path (hops) from　" +f_id+ "　to　" +t_id+ ":");
		Node node = null;
		String station_name = null;
		for(String station: stations){
			node = client.getNode(station);
			if(node.property.containsKey("name")){
				station_name = node.property.get("name");
			}
			System.out.println(station+ "\t" +station_name);
		}
		return;
	}
	
	public static void main(String[] args) throws Exception {
		
		Scanner scan = new Scanner(System.in);
		String source = scan.next();
		String target = scan.next();
		
		search_route(source, target);
		//search_route("0", "144");
	}
}