{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe world is in danger! Awful earthquakes are detected all over the world.\r\nHouses are destroyed, rivers overflow the banks, it is almost impossible to move from one city to another.\r\nSome roads are still useful, but even they became too steep because of soil movements.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFortunately, engineer Ivan has a car, which can go well uphill and downhill. But there are different gear-modes for\r\nmovement up and down, so during the driving you have to change gear-modes all the time. Also engineer Ivan has a good friend\u0026nbsp;–– geologist\r\nOrlov. Together they are able to invent a plan for world saving. But, unfortunately, geologist Orlov lives in another town.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIvan wants to save the world, but gear-box in his car started to wear out, so he doesn’t know, how long he will be able to use it.\r\nPlease help Ivan to save the world. Find a route to the Orlov\u0027s town, such that Ivan will have to change gear-modes as few times as possible. In the beginning of the way Ivan can turn on any of gear-modes and you don\u0027t have to count this action as a changing of gear-mode.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThere are two positive integer numbers \u003ci\u003en\u003c/i\u003e and \u003ci\u003em\u003c/i\u003e in the first line, the number of towns and roads\r\nbetween them respectively \u003cnobr\u003e(2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u0026nbsp;000;\u003c/nobr\u003e \u003cnobr\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 100\u0026nbsp;000).\u003c/nobr\u003e Next \u003ci\u003em\u003c/i\u003e lines contain two numbers each\u0026nbsp;— numbers of towns,\r\nwhich are connected by road. Moreover, the first is the town, which is situated below, from which you should go uphill by this road. Every road can be used for traveling in any of two directions.\r\nThere is at most one road between any two cities. In the last line there are numbers of two cities, in which\r\nIvan and geologist Orlov live, respectively. Although the majority of roads were destroyed, Ivan knows exactly, that the way to geologist Orlov\u0027s city exists.\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 the smallest number of gear-modes changes on the way to Orlov\u0027s city.\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\u003e3 2\r\n1 2\r\n3 2\r\n1 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\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\u003e3 3\r\n1 2\r\n2 3\r\n3 1\r\n1 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}