题目描述

给定一张 $n$ 个点 $m$ 条边的有向图，图中可能有重边与自环，求从 $1$ 号点出发，到 $n$ 号点的最短距离。

如果不能到达 $n$ 号点，输出 -1。

输入格式

第一行两个整数 $n$、$m$，表示点数和边数。$(1\le n,m\le 10^5)$

接下来 $m$ 行，每行两个整数 $u$、$v$，表示一条连接 $u$、$v$ 两点的有向边，边权为 $1$。$(1\le u,v\le n)$

输出格式

输出一个整数，表示从 $1$ 号点到 $n$ 号点的最短距离。

如果不能到达 $n$ 号点，输出 -1。

样例输入

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

样例输出

1