{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u003cstyle type\u003d\"text/css\"\u003e\r\n\u003cspan data-scayt_word\u003d\"h1\" data-scaytid\u003d\"1\"\u003eh1\u003c/span\u003e,\u003cspan data-scayt_word\u003d\"h2\" data-scaytid\u003d\"2\"\u003eh2\u003c/span\u003e,\u003cspan data-scayt_word\u003d\"h3\" data-scaytid\u003d\"3\"\u003eh3\u003c/span\u003e,\u003cspan data-scayt_word\u003d\"h4\" data-scaytid\u003d\"4\"\u003eh4\u003c/span\u003e,\u003cspan data-scayt_word\u003d\"h5\" data-scaytid\u003d\"5\"\u003eh5\u003c/span\u003e,\u003cspan data-scayt_word\u003d\"h6\" data-scaytid\u003d\"6\"\u003eh6\u003c/span\u003e{margin-bottom:0;}div.textBG p{margin: 0 0 0.0001pt;}\t\u003c/style\u003e\r\n\u003c/p\u003e\r\n\u003cdiv class\u003d\"Section1\"\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tA 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?\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tTo 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).\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tAssume that if a passenger takes a direct flight from \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:normal\"\u003eX\u003c/i\u003e\u003c/b\u003e to \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:normal\"\u003eY\u003c/i\u003e\u003c/b\u003e he never flies more than the geographical distance between \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:normal\"\u003eX\u003c/i\u003e\u003c/b\u003e and \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:normal\"\u003eY\u003c/i\u003e\u003c/b\u003e.\u003cspan style\u003d\"mso-spacerun: yes\"\u003e\u0026nbsp; \u003c/span\u003eThe geographical distance between two locations \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:\r\nnormal\"\u003eX\u003c/i\u003e\u003c/b\u003e and \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:normal\"\u003eY\u003c/i\u003e\u003c/b\u003e is the length of the geodetic line segment connecting \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:\r\nnormal\"\u003eX\u003c/i\u003e\u003c/b\u003e and \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003e\u003ci style\u003d\"mso-bidi-font-style:normal\"\u003eY\u003c/i\u003e\u003c/b\u003e. 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 \u003cspan style\u003d\"font-family: Symbol;\"\u003e\u003cspan style\u003d\"mso-char-type:symbol;mso-symbol-font-family:\r\nSymbol\"\u003ep\u003c/span\u003e\u003c/span\u003e\u003c!--[if supportFields]\u003e\u003cspan style\u003d\u0027mso-element:field-begin\u0027\u003e\u003c/span\u003ePRIVATE\r\n\u0026quot;TYPE\u003dPICT;ALT\u003d$\\pi$\u0026quot;\u003c![endif]--\u003e\u003c!--[if supportFields]\u003e\u003cspan\r\nstyle\u003d\u0027mso-element:field-end\u0027\u003e\u003c/span\u003e\u003c![endif]--\u003eis approximately \u003cb\u003e3.141592653589793\u003c/b\u003e. Round the geographical distance between every pair of cities to the nearest integer.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003e\u003cspan style\u003d\"font-size:14.0pt;mso-bidi-font-size:12.0pt\"\u003e\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cfont size\u003d\"5\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/font\u003e\u003cbr /\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tThe input may contain multiple test cases.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tThe first line of each test case contains three integers \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eN\u003c/b\u003e (N \u0026lt;\u003d 100), \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eM\u003c/b\u003e (M \u0026lt;\u003d 300) and \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eQ\u003c/b\u003e (Q \u0026lt;\u003d 10000) where \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eN\u003c/b\u003e indicates the number of cities, \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eM\u003c/b\u003e represents the number of direct flights and \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eQ\u003c/b\u003e is the number of queries.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tThe next \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003eN\u003c/b\u003e lines contain the city list. The \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003ei\u003c/b\u003e-th of these \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eN\u003c/b\u003e lines will contain a string \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e followed by two real numbers \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003elt\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eln\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, 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.)\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tThe next \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003eM\u003c/b\u003e lines contain the direct flight list. The \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003ei\u003c/b\u003e-th of these \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eM\u003c/b\u003e lines will contain two city names \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e indicating that there exists a direct flight from city \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e to city \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. Be assured that both city names will occur in the city list.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tThe next \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003eQ\u003c/b\u003e lines contain the query list. The \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003ei\u003c/b\u003e-th of these \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eQ\u003c/b\u003e lines will contain two city names \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e asking for the minimum distance a passenger needs to fly in order to get from city \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e to city \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. Be assured that \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ea\u003csub\u003ei\u003c/sub\u003e \u003cspan style\u003d\"mso-spacerun:\r\nyes\"\u003e\u0026nbsp;\u003c/span\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e are not equal and both city names will occur in the city list.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tThe input will terminate with three zeros form \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eN\u003c/b\u003e, \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eM\u003c/b\u003e and \u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003eQ\u003c/b\u003e.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003e\u003cspan style\u003d\"font-size:14.0pt;mso-bidi-font-size:12.0pt\"\u003e\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cfont size\u003d\"5\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/font\u003e\u003cbr /\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tFor 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 (\u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e) in the query to the second one (\u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e). If there exists no route form \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e to \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, just print the line \u0026quot;no route exists\u0026quot;.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;text-indent:.5in\"\u003e\r\n\t\tPrint a blank line between two consecutive test cases. \u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003e\u003cspan style\u003d\"font-size:14.0pt;mso-bidi-font-size:12.0pt\"\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\u003c!--[if !supportEmptyParas]--\u003e\t\t\u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003e\u003cspan style\u003d\"font-size:14.0pt;mso-bidi-font-size:12.0pt\"\u003e\u0026nbsp;\u003c!--[endif]--\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\t\u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003e\u003cfont size\u003d\"5\"\u003eSample Input\u003c/font\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cfont face\u003d\"courier\" size\u003d\"3\"\u003e3 4 2\u003cbr /\u003e\r\n\tDhaka 23.8500 90.4000\u003cbr /\u003e\r\n\tChittagong 22.2500 91.8333\u003cbr /\u003e\r\n\tCalcutta 22.5333 88.3667\u003cbr /\u003e\r\n\tDhaka Calcutta\u003cbr /\u003e\r\n\tCalcutta Dhaka\u003cbr /\u003e\r\n\tDhaka Chittagong\u003cbr /\u003e\r\n\tChittagong Dhaka\u003cbr /\u003e\r\n\tChittagong Calcutta\u003cbr /\u003e\r\n\tDhaka Chittagong\u003cbr /\u003e\r\n\t5 6 3\u003cbr /\u003e\r\n\tBaghdad 33.2333 44.3667\u003cbr /\u003e\r\n\tDhaka 23.8500 90.4000\u003cbr /\u003e\r\n\tFrankfurt 50.0330 8.5670\u003cbr /\u003e\r\n\tHong_Kong 21.7500 115.0000\u003cbr /\u003e\r\n\tTokyo 35.6833 139.7333\u003cbr /\u003e\r\n\tBaghdad Dhaka\u003cbr /\u003e\r\n\tDhaka Frankfurt\u003cbr /\u003e\r\n\tTokyo Hong_Kong\u003cbr /\u003e\r\n\tHong_Kong Dhaka\u003cbr /\u003e\r\n\tBaghdad Tokyo\u003cbr /\u003e\r\n\tFrankfurt Tokyo\u003cbr /\u003e\r\n\tDhaka Hong_Kong\u003cbr /\u003e\r\n\tFrankfurt Baghdad\u003cbr /\u003e\r\n\tBaghdad Frankfurt\u003cbr /\u003e\r\n\t0 0 0\u003cbr /\u003e\r\n\t\u003cbr /\u003e\r\n\t\u003c/font\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\t\u003cb style\u003d\"mso-bidi-font-weight:\r\nnormal\"\u003e\u003cfont size\u003d\"5\"\u003eSample Output\u003c/font\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cfont face\u003d\"courier\" size\u003d\"3\"\u003eCase #1\u003cbr /\u003e\r\n\t485 km\u003cbr /\u003e\r\n\t231 km\u003cbr /\u003e\r\n\t\u003cbr /\u003e\r\n\tCase #2\u003cbr /\u003e\r\n\t19654 km\u003cbr /\u003e\r\n\tno route exists\u003cbr /\u003e\r\n\t12023 km\u003cbr /\u003e\r\n\t\u003c/font\u003e\u003c/div\u003e\r\n\u003cp\u003e\r\n\t_________________________________________________________________________________________\u003c/p\u003e"}}]}