题目描述

给定一个简单有向图，包含编号从 $1$ 到 $N$ 的 $N$ 个顶点和 $M$ 条边。

第 $i$ 条边 $(1 \le i \le M)$ 是从顶点 $a_i$ 指向顶点 $b_i$ 的有向边。

请判断是否存在包含顶点 $1$ 的环，若存在，则找出所有此类环中边数的最小值。

输入格式

第一行，两个整数 $N$ 和 $M$，以空格分隔（$2 \le N \le 2 \cdot 10^5$，$1 \le M \le \min( \frac{N(N-1)}{2}, 2 \cdot 10^5 )$）。

接下来 $M$ 行，每行包含两个整数 $a_i$ 和 $b_i$，以空格分隔（$1 \le a_i, b_i \le N, a_i \neq b_i$）。

数据保证：对于任意 $i \neq j$ 均有 $(a_i, b_i) \neq (a_j, b_j)$。

输出格式

输出一个整数，表示答案。

样例

3 3
1 2
2 3
3 1

3

4 4
1 2
2 3
3 4
4 2

-1

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

4