The We-Ship-Cheap package shipping company is always interested in reducing their costs. They have decided that a computerized shipping route planner that determines the shortest shipping route between two cities would speed package delivery. We-Ship-Cheap services a number of different cities. They have established direct shipping links between pairs of cities. It is somewhat unusual that they have been able to create all the direct links with exactly the same distance. Unfortunately, since not every pair of cities is connected by a direct link, the shortest shipping route often involves travel through multiple intermediate cities. Write a program that given a collection of cities and links between them, and a shipping request, prints out the shortest shipping route for the given shipping request. Input The input file contains several test cases, each of them as described below. It will be a blank line between two consecutive The program takes as input a variable number of lines, each consisting of exactly two cities (identified by a two-uppercase-letter code and separated by a space). Each line identifies a bidirectional link that exists between the two cities. Following the link information will be a single shipping request that identifies a source and destination city. The first line of input will consist of a single integer that represents the number of links given in the input. The last line will contain the source and destination cities for which you are to find the minimal route. You may assume that the input is valid and consistent. Output For each test case, the program will produce as output a shortest shipping route (note that multiple minimum length routes may exist) between the two cities. If no route exists, the program should output ‘No route’ It will be a blank line between the output of two consecutive cases. Sample input 3 JV PT KA PT KA HP JV HP 2 JV PT KA HP JV HP Sample output JV PT PT KA
2/2 KA HP No route