← 返回题目列表

Codeforces · 601/A

A. 两条路线

中文机器翻译题面 查看原题

在荒诞斯坦,有 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。