J8 例题-9 佩奇的旅行1

题目描述

猪猪共和国拥有 $N$ 座城市，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$ ，通过每条道路都需要 $1$ 个时间。

使用道路 $i$，佩奇可以在一小时内从城市 $A_i$ 旅行到 $B_i$，或者从城市 $B_i$ 旅行到城市 $A_i$。

佩奇尽早从城市 $1$ 到达城市 $N$需要多少时间？

输入格式

第一行包含两个整数，图的顶点数 $N$ 和边数 $M$ ；

以下 $M$ 行中的每一行包含一对整数 $A_i$ 和 $B_i$，表示顶点 $A_i$ 和 $B_i$ 之间存在一条边 。对于每对顶点，它们之间最多有一条边，没有边将顶点连接到自身。

输出格式

一行，输出佩奇尽早从城市 $1$ 到达城市 $N$需要的时间。

样例输入1

4 5
2 4
1 2
2 3
1 3
3 4

样例输出1

2

样例输入2

7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7

样例输出2

4

样例分析

样例1中，从城市 $1$ 到城市 $4$ 所需的最短时间为 $2$ 小时，可以通过两条路径实现的：$1 \to 2 \to 4$ 和 $1\to 3\to 4$

数据范围

对于 $100\%$ 的数据有： $2 \le N \le 2000$，$0 \leq M \leq \min(2000,N(N-1)/2)$。