시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB26161376.471%

문제

Mr. Endo wanted to write the code that performs breadth-first search (BFS), which is a search algorithm to explore all vertices on a directed graph. An example of pseudo code of BFS is as follows:

1: current ← {start_vertex}
2: visitedcurrent
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:       foundfound ∪ {v}
8:   currentfoundvisited
9:   visitedvisitedfound

However, Mr. Endo apparently forgot to manage 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:       foundfound ∪ {v}
7:   currentfound

You may notice that for some graphs, Mr. Endo's program will not stop because it keeps running infinitely. Notice that it does not necessarily mean the program cannot explore all the vertices within finite steps. Your task here is to make a program that determines whether Mr. Endo's program will stop within finite steps for a given directed graph in order to point out the bug to him. Also, calculate the minimum number of loop iterations required for the program to stop if it is finite. Since the answer might be huge, thus print the answer modulo 109 + 7, which is a prime number.

입력

The input consists of a single test case formatted as follows.

N M
u1 v1
.
.
.
uM vM

The first line consists of two integers N (2 ≤ N ≤ 500) and M (1 ≤ M ≤ 200,000), where N is the number of vertices and M is the number of edges in a given directed graph, respectively. The i-th line of the following M lines consists of two integers ui and vi (1 ≤ ui, viN), which means there is an edge from ui to vi in the given graph. The vertex 1 is the start vertex, i.e. start_vertex in the pseudo codes. You can assume that the given graph also meets the following conditions.

  • The graph has no self-loop, i.e., uivi for all 1 ≤ iM.
  • The graph has no multi-edge, i.e., (ui, vi) ≠ (uj, vj) for all 1 ≤ i < jM.
  • 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 finite steps for the given input directed graph, print -1 in a line. Otherwise, print the minimum number of loop iterations required to stop modulo 109 + 7.

예제 입력 1

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