← 返回题目列表

AtCoder · jag2017autumn_i

I. 无尽BFS的复仇

中文机器翻译题面 查看原题

问题陈述

Endo 先生想要编写执行广度优先搜索 (BFS) 的代码,这是一种搜索算法,用于探索 指导 图表。 BFS的伪代码示例如下:

1: $当前 \leftarrow \{start\_vertex\}$ 2: $访问过 \leftarrow current$ 3: while $visited \ne$ 所有顶点的集合 4: $找到\leftarrow \{\}$ 5:对于 $u$ 在 $current$ 中 6:对于每个$v$,从$u$到$v$都有一条边 7: $找到 \leftarrow 找到 \cup \{v\}$ 8:$当前\leftarrow找到\setminus访问$ 9:$访问了\leftarrow访问了\cupfound$

然而,Endo 先生显然忘记了在他的代码中管理访问过的顶点。更准确地说,他编写了以下代码:

1: $当前 \leftarrow \{start\_vertex\}$ 2: while $current \ne$ 所有顶点的集合 3: $找到\leftarrow \{\}$ 4: 对于 $u$ 在 $current$ 中 5:对于每个$v$,从$u$到$v$都有一条边 6: $找到 \leftarrow 找到 \cup \{v\}$ 7:$当前\找到左箭头$

您可能会注意到,对于某些图表,远藤先生的程序不会停止,因为它会无限运行。请注意,这并不一定意味着程序无法在有限步骤内探索所有顶点。这里你的任务是编写一个程序,确定远藤先生的程序是否会在给定的有向图的有限步内停止,以便向他指出错误。另外,如果程序是有限的,则计算程序停止所需的最小循环迭代次数。由于答案可能很大,因此打印答案对 $10^9 + 7$ 取模,这是一个素数。


输入

输入由单个测试用例组成,格式如下。

$N$ $M$ $u_{1}$ $v_{1}$ $\vdots$ $u_{M}$ $v_{M}$

第一行由两个整数 $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}$。
  • 该图没有多边边,即 $(u_{i}, v_{i}) \ne (u_{j}, v_{j})$ 对于所有 $1 \le i < j \le M$。
  • 对于每个顶点 $v$,从起始顶点 $1$ 到 $v$ 至少有一条路径。

输出

如果 Endo 先生错误的 BFS 代码对于给定的输入有向图不能在有限步内停止,则打印 -1 一行。否则,打印停止模 $10^9 + 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