【模板】单源最短路1
题号:NC226492
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给你一个无向图,图中包含 5000 个点 m 个边,任意两个点之间的距离是 1 ,无重边或自环。请求出1号点到n号点的最短距离。

注意:图中可能存在孤立点,即存在点与任意点都没有边相连

如果1号点不能到达n号点,输出-1.

输入描述:

第一行两个整数n和m,表示图的点和边数。
接下来m行,每行两个整数u,v,表示u到v有一条无向边。

输出描述:

输出一行,表示1到n的最短路,如不存在,输出-1.
示例1

输入

复制
4 4
1 2
2 4
3 4
3 1

输出

复制
2
示例2

输入

复制
4 3
1 2
2 3
3 1

输出

复制
-1

说明

1号点不能到4号点。