在荒诞斯坦,有 n 个城镇(编号为 1 到 n)和 m 条双向铁路。还有一个极其简单的道路网络——对于每对不同的城镇 x 和 y,城镇 x 和 y 之间有一条双向道路,当且仅当它们之间没有铁路时。使用一条铁路或一条公路前往另一个城镇总是需要整整一小时。
一列火车和一辆公共汽车同时离开城镇 1。他们都有相同的目的地,n 镇,并且途中没有任何停留(但他们可以在 n 镇等待)。火车只能沿着铁路行驶,公共汽车只能沿着公路行驶。
您被要求规划车辆的路线;每条路线可以多次使用任何公路/铁路。要考虑的最重要的方面之一是安全——为了避免铁路道口发生事故,火车和公共汽车不得同时到达同一个城镇(n 城镇除外)。
在这些约束下,两辆车到达n镇所需的最短小时数(公交车和火车的最大到达时间)是多少?请注意,公共汽车和火车不需要同时到达城镇 n,但可以这样做。
输入
输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n - 1) / 2) – 分别是城镇数量和铁路数量。
接下来的 m 行中的每一行都包含两个整数 u 和 v,表示城镇 u 和 v 之间的铁路(1 ≤ u,v ≤ n,u ≠ v)。
您可以假设最多有一条铁路连接任意两个城镇。
输出
输出一个整数——后一辆车到达n镇的最小可能时间。如果至少一辆车不可能到达城镇 n,则输出 - 1。
示例
输入 #1
4 2 1 3 3 4
输出 #1
2
输入 #2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
输出 #2
-1
输入 #3
5 5 4 2 3 5 4 5 5 1 1 2
输出 #3
3
注意
在第一个示例中,火车可以采取路线 $$1 \rightarrow 3 \rightarrow 4$$,公共汽车可以采取路线 $$1 \rightarrow 2 \rightarrow 4$$。请注意,他们可以同时到达城镇 4。
在第二个样本中,荒诞斯坦由铁路工人统治。没有道路,所以公共汽车无法到达镇 4。