| We Ship Cheap |
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.
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 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''
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.
If there are two or more test cases, it will be a blank line between two consecutive, both in input and output files.
3 JV PT KA PT KA HP JV HP 2 JV PT KA HP JV HP
JV PT PT KA KA HP No route