{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/AUG14/mandarin/REVERSE.pdf\" rel\u003d\"nofollow noreferrer noopener\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/AUG14/russian/REVERSE.pdf\" rel\u003d\"nofollow noreferrer noopener\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\n\n\u003cp\u003eSometimes mysteries happen. Chef found a directed graph with \u003cb\u003eN\u003c/b\u003e vertices and \u003cb\u003eM\u003c/b\u003e edges in his kitchen! \u003c/p\u003e\n\u003cp\u003eThe evening was boring and chef has nothing else to do, so to entertain himself, Chef thought about a question \"What is the minimum number of edges he needs to reverse in order to have at least one path from vertex \u003cb\u003e1\u003c/b\u003e to vertex \u003cb\u003eN\u003c/b\u003e, where the vertices are numbered from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e.\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eEach test file contains only one test case.\u003c/p\u003e\n\u003cp\u003eThe first line of the input contains two space separated integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eM\u003c/b\u003e, denoting the number of vertices and the number of edges in the graph respectively. The \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e line of the next \u003cb\u003eM\u003c/b\u003e lines contains two space separated integers \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, denoting that the \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e edge connects vertices from \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e to \u003cb\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eIn a single line, print the minimum number of edges we need to revert. If there is no way of having at least one path from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e, print \u003cb\u003e-1\u003c/b\u003e.\u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\u003cli\u003e\u003cb\u003e1 ≤ N, M ≤ 100000 \u003d 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ X\u003csub\u003ei\u003c/sub\u003e, Y\u003csub\u003ei\u003c/sub\u003e ≤ N\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003eThere can be multiple edges connecting the same pair of vertices, There can be self loops too i.e. \u003cb\u003e X\u003csub\u003ei\u003c/sub\u003e \u003d Y\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003c/li\u003e\n\u003c/ul\u003e"}},{"title":"Sample 1","value":{"format":"MD","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 7\n1 2 \n3 2\n3 4\n7 4\n6 2\n5 6\n7 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003eWe can consider two paths from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003e7\u003c/b\u003e:\u003c/p\u003e\n\u003cul\u003e\u003cli\u003e \u003cb\u003e1-2-3-4-7\u003c/b\u003e \u003c/li\u003e\n\u003cli\u003e \u003cb\u003e1-2-6-5-7\u003c/b\u003e \u003c/li\u003e\n\u003c/ul\u003e\u003cp\u003eIn the first one we need to revert edges \u003cb\u003e(3-2), (7-4)\u003c/b\u003e. In the second one - \u003cb\u003e(6-2), (5-6), (7-5)\u003c/b\u003e. So the answer is \u003cb\u003emin(2, 3) \u003d 2\u003c/b\u003e.\u003c/p\u003e\n"}}]}