A leading airline has hired you to write a program that answers the following query: given lists of city locations and direct flights, what is the minimum distance a passenger needs to fly to get from one given city to another? The city locations are specified by latitude and longitude.
To get from a city to another a passenger may take a direct flight if one exists; otherwise he must take a sequence of connecting flights.
Assume that if a passenger takes a direct flight from X to Y he never flies more than the geographical distance between X and Y. The geographical distance between two locations X and Y is the length of the geodetic line segment connecting X and Y. The geodetic line segment between two points on a sphere is the shortest connecting curve lying entirely on the surface of the sphere. Assume that the Earth is a perfect sphere of radius exactly 6,378 km, and that the value of is approximately 3.141592653589793. Round the geographical distance between every pair of cities to the nearest integer.
The input may contain multiple test cases. The first line of each test case contains three integers N<=100, M<=300, and Q 10,000, where N indicates the number of cities, M represents the number of direct flights, and Q is the number of queries.
The next N lines contain the list of cities. The ith of these lines contains a string ci followed by two real numbers lti and lni, representing the city name, latitude, and longitude, respectively. The city name will be at most 20 characters and will not contain white-space characters. The latitude will be between -90 (South Pole) and +90 (North Pole). The longitude will be between -180 and +180, where negative (positive) numbers denote locations west (east) of the meridian passing through Greenwich, England.
The next M lines contain the direct flight list. The ith of these lines contains two city names aai and bi, indicating that there exists a direct flight from city ai to city bi. Both city names will occur in the city list.
The next Q lines contain the query list. The ith of these lines will contain city names ai and bi asking for the minimum distance a passenger needs to fly to get from ai to bi. Be assured that ai and bi are not equal and both city names will occur in the city list.
The input will terminate with three zeros for N, M, and Q.
For each test case, first output the test case number (starting from 1) as shown in the sample output. Then for each input query, print a line giving the shortest distance (in km) a passenger needs to fly to get from the first city (ai) to the second one (bi). If there exists no route form ai to bi, just print the line “no route exists''.
Print a blank line between two consecutive test cases.
3 4 2 Dhaka 23.8500 90.4000 Chittagong 22.2500 91.8333 Calcutta 22.5333 88.3667 Dhaka Calcutta Calcutta Dhaka Dhaka Chittagong Chittagong Dhaka Chittagong Calcutta Dhaka Chittagong 5 6 3 Baghdad 33.2333 44.3667 Dhaka 23.8500 90.4000 Frankfurt 50.0330 8.5670 Hong_Kong 21.7500 115.0000 Tokyo 35.6833 139.7333 Baghdad Dhaka Dhaka Frankfurt Tokyo Hong_Kong Hong_Kong Dhaka Baghdad Tokyo Frankfurt Tokyo Dhaka Hong_Kong Frankfurt Baghdad Baghdad Frankfurt 0 0 0
Case #1 485 km 231 km Case #2 19654 km no route exists 12023 km