CF601A.The Two Routes

In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y, there is a bidirectional road between towns x and y if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.

A train and a bus leave town 1 at the same time. They both have the same destination, town n, and don't make any stops on the way (but they can wait in town n). The train can move only along railways and the bus can move only along roads.

You've been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n) simultaneously.

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town n (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town n at the same moment of time, but are allowed to do so.

在荒诞国（Absurdistan），共有 $n$ 个城镇（编号为 $1$ 至 $n$）和 $m$ 条双向铁路。此外，还存在一个极其简单的公路网络：对任意两个不同的城镇 $x$ 和 $y$，当且仅当 $x$ 与 $y$ 之间没有铁路连接时，才存在一条连接 $x$ 和 $y$ 的双向公路。无论乘坐铁路还是公路前往另一个城镇，耗时均为恰好一小时。

一列火车和一辆公交车同时从城镇 $1$ 出发，目的地均为城镇 $n$，途中均不作停留（但可在城镇 $n$ 等待）。火车只能沿铁路行驶，而公交车只能沿公路行驶。

你需要为这两种交通工具规划行驶路线；每条路线均可多次重复使用任意公路或铁路。其中一项最重要的考量因素是安全性——为避免在铁路道口发生事故，火车与公交车不得同时抵达同一座城镇（城镇 $n$ 除外）。

在上述约束条件下，两者均抵达城镇 $n$ 所需的最短时间（即公交车与火车到达时间中的较大值）是多少？注意：公交车与火车不必在同一时刻抵达城镇 $n$，但允许如此。

The first line of the input contains two integers n and m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n - 1) / 2) — the number of towns and the number of railways respectively.

Each of the next m lines contains two integers u and v, denoting a railway between towns u and v (1 ≤ u, v ≤ n, u ≠ v).

You may assume that there is at most one railway connecting any two towns.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 400$，$0 \leq m \leq n(n-1)/2$），分别表示城镇的数量和铁路的数量。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$，表示城镇 $u$ 与城镇 $v$ 之间有一条铁路（$1 \leq u, v \leq n$，$u \neq v$）。

你可以假设任意两个城镇之间至多只有一条铁路相连。

Output one integer — the smallest possible time of the later vehicle's arrival in town n. If it's impossible for at least one of the vehicles to reach town n, output  - 1.

输出一个整数——即较晚到达城镇 $n$ 的车辆的最早可能到达时间。若至少有一辆车辆无法到达城镇 $n$，则输出 $-1$。

In the first sample, the train can take the route and the bus can take the route . Note that they can arrive at town 4 at the same time.

In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there's no way for the bus to reach town 4.

在第一个样例中，火车可以走路线 ，而公交车可以走路线 。注意，它们可以同时抵达第 4 号城镇。

在第二个样例中，Absurdistan 由铁路工人统治。该国没有公路，因此公交车无法到达第 4 号城镇。