{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"在一个叫奥斯汀的城市,有 $n$ 个小镇(从 $1$ 到 $n$ 编号),一些小镇通过 $m$ 条双向火车铁轨相连。为了保证每两个小镇之间的人可以方便的相互访问,市长就在那些没有铁轨直接相连的小镇之间建造了公路。在两个直接通过公路或者铁路相连的小镇之间移动,要花费一个小时的时间。\r\n\r\n现在有一辆火车和一辆汽车同时从小镇 $1$ 出发。他们都要前往小镇 $n$ ,但是他们中途不能同时停在同一个小镇(但是可以同时停在小镇 $n$ )。火车只能走铁路,汽车只能走公路。\r\n\r\n现在请来为火车和汽车分别设计一条线路;所有的公路或者铁路可以被多次使用。使得火车和汽车尽可能快的到达小镇 $n$ 。即要求他们中最后到达小镇 $n$ 的时间要最短。输出这个最短时间。(最后火车和汽车可以同时到达小镇 $n$ ,也可以先后到达。)\r\n\r\n样例解释:\r\n\r\n在样例中,火车可以按照 $1\\longrightarrow3\\longrightarrow4$ 行驶,经过 $2$ 小时后到达小镇 $4$ 。汽车 $1\\longrightarrow4$ 按照行驶,经过 $1$ 小时后到达小镇 $4$ 。"}},{"title":"Input","value":{"format":"MD","content":"单组测试数据。\r\n第一行有两个整数 $n$ 和 $m (2\\le n\\le 400, 0\\le m\\le n\\times (n-1)/2)$ ,表示小镇的数目和铁轨的数目。\r\n接下来 $m$ 行,每行有两个整数 $u$ 和 $v$ ,表示 $u$ 和 $v$ 之间有一条铁路。 $(1\\le u,v\\le n, u\\neq v)$ 。\r\n输入中保证两个小镇之间最多有一条铁路直接相连。"}},{"title":"Output","value":{"format":"MD","content":"输出一个整数,表示答案,如果没有合法的路线规划,输出 $-1$ 。"}},{"title":"Data Description","value":{"format":"MD","content":"对于 $10\\%$ 的数据, $m\u003d0$ ; \r\n对于 $40\\%$ 的数据, $2\\le n\\le 20$ ; \r\n对于 $100\\%$ 的数据, $2\\le n\\le 400$ , $0\\le m\\le n\\times (n-1)/2$ ;"}},{"title":"Sample 1","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\u003e4 2\n1 3\n3 4\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"}}]}