{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFew people know, but a long time ago a developed state existed on Mars. It \r\nconsisted of \u003ci\u003en\u003c/i\u003e cities, numbered by integers from 1 to \u003ci\u003en\u003c/i\u003e, the capital had \r\nthe number 1. Some pairs of cities were connected by a road. The residents \r\nof the state were very prudent, therefore, between any two cities, there \r\nwas exactly one path (possibly consisting of several roads). \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eDue to the fact that the state was developed, its residents loved \r\ntraveling. Tourist route on Mars was described by two numbers \u003ci\u003eL\u003c/i\u003e and \r\n\u003ci\u003eR\u003c/i\u003e. This meant that the tourist started the route in the city \u003ci\u003eL\u003c/i\u003e, then \r\nwent to the city \u003ci\u003eL\u003c/i\u003e + 1 (without going into the cities, that did not lie on \r\nthe path between \u003ci\u003eL\u003c/i\u003e and \u003ci\u003eL\u003c/i\u003e + 1), then went to the city \u003ci\u003eL\u003c/i\u003e + 2, and so \r\non. The last city on the route was the city \u003ci\u003eR\u003c/i\u003e. A city that was the \r\nclosest to the capital among all cities visited on this route (if to count \r\na distance between the cities by the roads) was considered \u003ci\u003e the main \r\nattraction\u003c/i\u003e of the route. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eKnowing the map of the Martian state and all the tourist routes, find for \r\neach route its main attraction. \u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains an integer \u003ci\u003en\u003c/i\u003e that is the number of cities (1 \r\n≤ \u003ci\u003en\u003c/i\u003e ≤ 2 · 10\u003csup\u003e5\u003c/sup\u003e). \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe following \u003ci\u003en\u003c/i\u003e − 1 lines describe the roads. Each road is described by \r\ntwo numbers of cities that are connected by it (1\u0026nbsp;≤\u0026nbsp;\u003ci\u003ev\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e,\u0026nbsp;\u003ci\u003eu\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u0026nbsp;≤\u0026nbsp;\u003ci\u003en\u003c/i\u003e; \u003ci\u003ev\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u0026nbsp;≠\u0026nbsp;\u003ci\u003eu\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e). \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe (\u003ci\u003en\u003c/i\u003e + 1)-th line contains an integer \u003ci\u003eq\u003c/i\u003e that is the number of \r\ntourist routes (0 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e). \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThen \u003ci\u003eq\u003c/i\u003e lines describe the routes themselves. Each route is described by \r\na pair of integers \u003ci\u003eL\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eR\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e (1 ≤ \u003ci\u003eL\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003eR\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e). \u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput \u003ci\u003eq\u003c/i\u003e integers, one per line\u0026nbsp;—\u0026nbsp;for each route the number of its \r\nmain attraction. These numbers should be output in the same order in which \r\nthe respective routes were described. \u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n1 2\r\n1 3\r\n2 4\r\n2 5\r\n2 6\r\n3 7\r\n3\r\n4 6\r\n3 4\r\n5 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n1 3\r\n3 5\r\n5 6\r\n7 5\r\n1 4\r\n2 4\r\n3\r\n4 5\r\n5 6\r\n6 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5\r\n5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Notes","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThis problem has a big input and output data size and a strict Time Limit. If you write your solution in C++ we recommend you to use Visual C++ 2013 compiler.\u003c/div\u003e\u003c/div\u003e"}}]}