给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边或自环。

所有边的长度均为 1，点的编号为 $1$ ~ $n$

请你求出从 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点到 $n$ 号点，输出 $-1$

输入格式

第一行包含两个正整数 $n, m$ ($1 \leq n, m \leq 100000)$

接下来 $m$ 行，每行包含两个正整数 $a, b$，表示存在一条从 $a$ 抵达 $b$ 的长度为1的边

输出格式

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

样例 1

输入：

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

输出：

1

来源：Luogu_U572606。本站使用重新构建的测试数据。