问题描述

有一个简单的有向图，它有 $N$ 个点，编号从 $1$ 到 $N$，有 $M$ 条边。第 $i(1\leq i\leq M)$ 条边是从点 $a_i$ 到点 $b_i$ 的有向边。

确定是否存在包含点 1 的环，如果存在，则输出满足要求的环的最小边数。

数据规模

$2\leq N\leq 2×10^5$

$1\leq M\leq\min\left(\frac{N(N-1)}{2},2×10^5\right)$

$1\leq a_i\leq N$

$1\leq b_i\leq N$

$a_i\neq b_i$

$(a_i,b_i)\neq(a_j,b_j)$ 和 $(a_i,b_i)\neq(b_j,a_j)$，如果 $i\neq j$。

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$N\ M$

$a_1\ b_1$

$a_2\ b_2$

$\vdots$

$a_M\ b_M$

输出

如果存在包含点 1 的环，则打印环中的最小边数。否则，打印 -1。

3 3
1 2
2 3
3 1

3

点 1 到点 2 到点 3 到点 1 是一个有三条边的环，这是唯一一个包含点 1 的环。

3 2
1 2
2 3

-1

6 9
6 1
1 5
2 6
2 1
3 6
4 2
6 4
3 5
5 4

4