끝나지 않는 BFS의 역습

엔도 씨는 방향 그래프의 모든 정점을 탐색하는 알고리즘인 너비 우선 탐색(BFS) 코드를 작성하려고 했다. BFS의 의사 코드 예시는 다음과 같다.

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

그런데 엔도 씨는 방문한 정점을 관리하는 부분을 빠뜨린 모양이다. 정확히는 다음과 같은 코드를 작성했다.

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

어떤 그래프에서는 엔도 씨의 프로그램이 끝없이 실행되며 멈추지 않는다. 다만 그렇다고 해서 이 프로그램이 유한 번의 단계 안에 모든 정점을 탐색하지 못한다는 뜻은 아니다. 엔도 씨에게 버그를 알려 주기 위해, 주어진 방향 그래프에서 엔도 씨의 프로그램이 유한 번의 단계 안에 멈추는지 판정하는 프로그램을 작성하라. 멈춘다면 프로그램이 멈출 때까지 필요한 최소 루프 반복 횟수도 구하라. 답이 매우 클 수 있으므로 소수인 $10^9 + 7$로 나눈 나머지를 출력한다.

입력은 하나의 테스트 케이스로 이루어지며 형식은 다음과 같다.

N M
u1 v1
.
.
.
uM vM

첫째 줄에 두 정수 $N$ ($2 \le N \le 500$)과 $M$ ($1 \le M \le 200{,}000$)이 주어진다. $N$은 방향 그래프의 정점 수이고 $M$은 간선 수다. 이어지는 $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$로 가는 경로가 적어도 하나 있다.

주어진 방향 그래프에서 엔도 씨의 잘못된 BFS 코드가 유한 번의 단계 안에 멈추지 않으면 -1을 한 줄에 출력한다. 그렇지 않으면 멈출 때까지 필요한 최소 루프 반복 횟수를 $10^9 + 7$로 나눈 나머지를 출력한다.