Problem A

Airlines

Input: standard input

Output: standard output

 

A leading airlines company has hired you to write a program that answers the following query: given a list of city locations (latitudes and longitudes) and a list of direct flights what is the minimum distance a passenger needs to fly to get from a given city to another?

 

To get from a city to another a passenger may either take a direct flight (if exists) or take a sequence of connecting flights (if there exists such a route).

 

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 in the surface of the sphere. Assume that the Earth is a perfect sphere with a radius of exactly 6378-km and the value of p is approximately 3.141592653589793. Round the geographical distance between every pair of cities to the nearest integer.

 

Input

The input may contain multiple test cases.

 

The first line of each test case contains three integers N (N <= 100), M (M <= 300) and Q (Q <= 10000) 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 city list. The i-th of these N lines will contain a string c_i followed by two real numbers lt_i and ln_i, representing the city name, its latitude and longitude respectively. The city name will be no longer than 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 numbers denote locations west of the meridian and positive numbers denote locations east of the meridian. (The meridian passes through Greenwich, London.)

 

The next M lines contain the direct flight list. The i-th of these M lines will contain two city names a_i and b_i indicating that there exists a direct flight from city a_i to city b_i. Be assured that both city names will occur in the city list.

 

The next Q lines contain the query list. The i-th of these Q lines will contain two city names a_i and b_i asking for the minimum distance a passenger needs to fly in order to get from city a_i to city b_i. Be assured that a_i  b_i are not equal and both city names will occur in the city list.

 

The input will terminate with three zeros form N, M and Q.

 

Output

For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then for each query in the input print a line giving the shortest distance (in km) a passenger needs to fly to get from the first city (a_i) in the query to the second one (b_i). If there exists no route form a_i to b_i, just print the line "no route exists".

Print a blank line between two consecutive test cases.

 

Sample Input

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

Sample Output

Case #1
485 km
231 km

Case #2
19654 km
no route exists
12023 km