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 π 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 ci followed by two real numbers lti and lni, 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 ai and bi indicating that there exists a direct flight from city ai to city bi. 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 ai and bi asking for the minimum distance a passenger needs to fly in order to get from city ai to city bi. Be assured that aibi 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 (ai) in the query 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. Sample Input 342 Dhaka 23.8500 90.4000 Chittagong 22.2500 91.8333 Calcutta 22.5333 88.3667
2/2 Dhaka Calcutta Calcutta Dhaka Dhaka Chittagong Chittagong Dhaka Chittagong Calcutta Dhaka Chittagong 563 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 000 Sample Output Case #1 485 km 231 km Case #2 19654 km no route exists 12023 km