Driving Distances

file: paths.cc


In swamp county there are a number of small towns connected by one-way roads. The speed limit on all of the roads is 75mph, and everybody in the county pretty much drives the limit. (In fact, Swamp county's main source of revenue is the tickets given to out-of-towners for holding up traffic around the more precipitous curves). The county comptroller is investigating a web-based service to help county dwellers get from place to place as quickly as possible, and due to the ever-changing landscape (roads have been known to be swallowed whole during particularly fierce downpours), she would like a flexible system that does not presume that any particular roads are in service.

The problem You have been contracted to write a program that takes a list of the roads in service (and their distances) as input and then answers queries about the driving distance between any two Swamp county towns. The input will consist of a number of road-specification lines:

Starting Town        Destination Town         Distance
followed by a number of query lines:
Starting Town        Destination Town
Your program should output one line per query line, indicating the shortest driving distance from the Starting Town to the Destination Town. You should assume that the driving distance from any town to itself is 0.

Input/Output Specification More precisely, the input file will consist of one or more road-specification lines, followed by a line with the single word queries, followed by one or more lines, each with two towns that appeared in the previous road-specifications. If the Destination Town is reachable from the Starting Town, your program should print the distance of the shortest path from the latter to the former. If the Destination Town is not reachable from the Starting Town, your program should print

Not Reachable
instead of the shortest distance. In each road-specification line the Starting Town and Destination Town will be strings of letters (whose first letter is capitalized) delimited by one or more spaces. All of the Distances in the read-specification lines will be integers, though not necessarily positive (or even nonnegative) integers -- in a place like Swamp County, time can swerve as unpredicatably as the drivers. No town name will be more than 50 letters long.

After all of the queries from a particular set of road-specifications, the line

end of queries
will appear, potentially followed by another problem instance. Your output should include a blank line to separate the output of different problem instances.

Example Input

Albuquerque Baltimore  8
Albuquerque Chicago   13
Albuquerque Eastport   1
Baltimore Denver       6
Baltimore Eastport    12
Chicago Baltimore      9
Denver Albuquerque     7
Denver Chicago         0
Eastport Denver       11
Eastport Faraway      77
Albuquerque Denver
Eastport Albuquerque
Faraway Denver
Baltimore Chicago
end of queries
Wallawalla Vancouver  8
Wallawalla Vancouver
end of queries

Example Output

Not Reachable