题目描述

有一个简单有向图，包含 $N$ 个节点和 $M$ 条边。其中第 $i$ 条边从节点 $a_i$ 指向 $b_i$ 。

判断是否存在包含节点 $1$ 的环。如果存在，求这些环中边数的最小值。

输入格式

第一行是空格分隔的两个整数： $N\ M$ ；

之后 $M$ 行，每行是空格分隔的两个整数 $a_i,b_i$

输出格式

一个整数。若存在包含节点 $1$ 的环，输出环包含的边数的最小值；否则，输出 $-1$ 。

3 3
1 2
2 3
3 1

3

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 \leq N \leq 2 \times 10^5$ ；
• $1 \leq M \leq \min \big( \frac{N(N-1)}{2}, 2 \times 10^5 \big)$ ；
• 给定的图没有重边和自环