Revenge of the Endless BFS

Mr. Endo wanted to write code that performs breadth-first search (BFS), a search algorithm that explores every vertex of a directed graph. An example of BFS in pseudo code follows.

1: current ← {start_vertex}
2: visited ← current
3: while visited ≠ the set of all the vertices
4:   found ← {}
5:   for u in current
6:     for each v such that there is an edge from u to v
7:       found ← found ∪ {v}
8:   current ← found ∖ visited
9:   visited ← visited ∪ found

However, Mr. Endo apparently forgot to manage the visited vertices in his code. More precisely, he wrote the following code.

1: current ← {start_vertex}
2: while current ≠ the set of all the vertices
3:   found ← {}
4:   for u in current
5:     for each v such that there is an edge from u to v
6:       found ← found ∪ {v}
7:   current ← found

For some graphs, Mr. Endo's program never stops and keeps running forever. Note that this does not necessarily mean the program cannot explore all the vertices within a finite number of steps. To point out the bug to him, write a program that decides whether Mr. Endo's program stops within a finite number of steps for a given directed graph. If it stops, also compute the minimum number of loop iterations the program needs before it stops. Since the answer might be huge, print it modulo $10^9 + 7$, which is a prime number.

The input consists of a single test case in the following format.

N M
u1 v1
.
.
.
uM vM

The first line contains two integers $N$ ($2 \le N \le 500$) and $M$ ($1 \le M \le 200{,}000$), where $N$ is the number of vertices and $M$ is the number of edges of the directed graph. The $i$-th of the following $M$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$), which means there is an edge from $u_i$ to $v_i$. Vertex 1 is the start vertex, that is, start_vertex in the pseudo code. The given graph also satisfies the following conditions.

• The graph has no self-loop, that is, $u_i \ne v_i$ for all $1 \le i \le M$.
• The graph has no multi-edge, that is, $(u_i, v_i) \ne (u_j, v_j)$ for all $1 \le i < j \le M$.
• For each vertex $v$, there is at least one path from the start vertex 1 to $v$.

If Mr. Endo's wrong BFS code cannot stop within a finite number of steps for the given directed graph, print -1 on a line. Otherwise, print the minimum number of loop iterations needed before it stops, modulo $10^9 + 7$.