题目描述

有一个小镇一共有 $N$ 个路口，编号从 $1$ 到 $N$。路口之间有 $M$ 条单向通行的道路，第 $i$ 条道路从路口 $a_i$ 通往路口 $b_i$。保证图中没有自环，并且任意两条边的有序对互不相同。

现在小蓝想检查：以小镇的中心路口—— $1$ 号路口为起点，是否存在一条从 $1$ 号路口出发最后又回到 $1$ 号路口的环路？如果存在，请求出所有经过 $1$ 号路口的环路中，道路数量最少的那个环路的边数；如果不存在，输出 -1。

输入格式

第一行两个正整数 $N, M$，分别表示路口总数和单向道路总数。

接下来 $M$ 行，每行两个正整数 $a_i, b_i$，表示一条从 $a_i$ 指向 $b_i$ 的有向边。

输出格式

输出一行一个整数，包含 $1$ 号路口的最短环路的边数。如果不存在这样的环路，输出 -1。

3 3
1 2
2 3
3 1

3

样例 1 解释说明

路径 $1 \to 2 \to 3 \to 1$ 是一条有 $3$ 条边的环路，这是经过 $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)$
• $a_i \neq b_i$
• 所有输入数值均为整数