MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});  

### 问题描述

Endo 先生想要编写一个执行广度优先搜索（BFS）的代码，这是一种用来探索有向图上所有顶点的搜索算法。BFS 的伪代码示例如下：

> 1: $current \\leftarrow \\{start\\_vertex\\}$ 2: $visited \\leftarrow current$ 3: while $visited \\ne$ 所有顶点的集合 4: $found \\leftarrow \\{\\}$ 5: 对于每个 $u$ 在 $current$ 中 6: 对于每个由 $u$ 指向 $v$ 的边 7: $found \\leftarrow found \\cup \\{v\\}$ 8: $current \\leftarrow found \\setminus visited$ 9: $visited \\leftarrow visited \\cup found$

然而，Endo 先生显然忘记在他的代码中管理已访问的顶点。更确切地说，他写了以下代码：

> 1: $current \\leftarrow \\{start\\_vertex\\}$ 2: while $current \\ne$ 所有顶点的集合 3: $found \\leftarrow \\{\\}$ 4: 对于每个 $u$ 在 $current$ 中 5: 对于每个由 $u$ 指向 $v$ 的边 6: $found \\leftarrow found \\cup \\{v\\}$ 7: $current \\leftarrow found$

你可能会注意到，对于某些图来说，Endo 先生的程序不会停止，因为它将无限运行下去。请注意，这并不一定意味着这个程序不能在有限步骤内探索所有顶点。你的任务是编写一个程序，在给定的有向图中确定 Endo 先生的程序是否会在有限步骤内停止，以便向他指出错误。同时，如果程序是有限的，则计算停止所需的最小循环迭代次数。由于答案可能很大，因此输出答案模 $10^9 + 7$，即一个质数。

* * *

### 输入

输入包含一个单独的测试用例，格式如下。

> $N$ $M$ $u_1$ $v_1$ $\dots$ $u_M$ $v_M$

第一行包含两个整数 $N$（$2 \le N \le 500$）和 $M$（$1 \le M \le 200,000$），分别表示给定有向图中的顶点数和边数。接下来的 $M$ 行中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le N$），表示给定图中从 $u_i$ 到 $v_i$ 有一条边。顶点 $1$ 是起始顶点，即伪代码中的 $start\_vertex$。你可以假设给定的图还满足以下条件。

* 图中不存在自环，即对于所有 $1 \le i \le M$ 都有 $u_i \ne v_i$。
* 图中不存在重边，即对于所有 $1 \le i < j \le M$ 都有 $(u_i, v_i) \ne (u_j, v_j)$。
* 对于每个顶点 $v$，从起始顶点 $1$ 到 $v$ 至少存在一条路径。

### 输出

如果 Endo 先生错误的 BFS 代码在给定的输入有向图中不能在有限步骤内停止，输出一行 `-1`。否则，输出使程序停止所需的最小循环迭代次数，结果模 $10^9 + 7$。

* * *

### 示例输入 1

```plain
4 4
1 2
2 3
3 4
4 1

示例输出 1

-1

示例输入 2

4 5
1 2
2 3
3 4
4 1
1 3

示例输出 2

7

示例输入 3

5 13
4 2
2 4
1 2
5 4
5 1
2 1
5 3
4 3
1 5
4 5
2 3
5 2
1 3

示例输出 3

3