环

题目描述

有一个简单有向图,包含编号为 $1$ 到 $N$ 的 $N$ 个顶点和 $M$ 条边。第 $i$ 条边($1 \le i \le M$)是从顶点 $a_i$ 到顶点 $b_i$ 的有向边。

判断是否存在包含顶点 $1$ 的环,如果存在,求出所有这样的环中最小的边数。

输入格式

输入按以下格式从标准输入给出:

$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 \to$ 顶点 $2 \to$ 顶点 $3 \to$ 顶点 $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

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le \min \left( \frac{N(N-1)}{2},\ 2 \times 10^5 \right)$
• $1 \le a_i \le N$
• $1 \le b_i \le N$
• $a_i \neq b_i$
• 当 $i \neq j$ 时,$(a_i, b_i) \neq (a_j, b_j)$ 且 $(a_i, b_i) \neq (b_j, a_j)$。
• 所有输入值均为整数。