The motivation for this problem is a directionally impaired friend, who doesn't care about the shortest or quickest routes -- instead, easier is better. Your task is to read the map information from a database of the entire country and produce the route with the smallest number of roads to use for a trip between an origin city and a destination city. You are guaranteed that there will be a path between origin and destination for any query asked.
The input consists of multiple cases. The input for each case consists of three
sections: the first lists the cities, the second lists the roads, and the third lists the
queries. Each case starts with an integer C (1 <= C <= 200) that represents the
number of cities, followed by C lines each containing the name of a city. There is no white space in a city's name.
The next line consists of an integer R (1 <= R <= 100) that represents the number of roads followed by R lines each describing a road. Each road description has the following form:
<RoadName> <CityA> <AB Distance> <CityB>[ <BC Distance> <CityC>[…]]
There is no white space in a road's name. Roads may pass through any number of cities. The cities appear in the order the road passes through them, and no road passes through the same city more than once. Roads are bidirectional. The
distance (an integer number) it takes to follow a road between each pair of cities is the distance listed between these two names.
The next line consists of an integer Q (1 < Q < 100) that represents the number of queries followed by Q lines each describing a query. Each query description has the following form: <origin> <destination>, where <origin> and <destination> are the names of cities.
A case with C equals zero (0) terminates the input data, and should not be processed.
For each query, the output consists of a single line of the following form:
Number of roads needed from <origin> to <destination> is <number>.
<origin> and <destination> are the names of cities, and <number> is the smallest
number of roads needed for the trip.
OR Adelaide 300 Melbourne
HH Melbourne 850 WestSydney 105 Sydney
M7 WestSydney 1130 Brisbane
BushTrack Adelaide 2448 Brisbane
Output for the Sample Input
Number of roads needed from Adelaide to Brisbane is 1.
The Bush Track connects Adelaide and Brisbane, so it is the only road needed.
Note that if there were only 3 roads (OR, HH and M7), all 3 would need to be used.
The traveller would have to take OR from Adelaide to Melbourne, HH from
Melbourne to WestSydney, then M7 from WestSydney to Brisbane.