问题陈述
Endo 先生想要编写执行广度优先搜索 (BFS) 的代码,这是一种探索无向图上所有顶点的搜索算法。 BFS的伪代码示例如下:
1: $当前 \leftarrow \{start\_vertex\}$ 2: $访问过 \leftarrow current$ 3: while $visited \ne$ 所有顶点的集合 4: $找到\leftarrow \{\}$ 5:对于$current$中的$v$ 6:对于与$v$相邻的每个$u$ 7: $找到 \leftarrow 找到 \cup \{u\}$ 8:$当前\leftarrow找到\setminus访问$ 9:$访问了\leftarrow访问了\cupfound$
然而,Endo 先生显然忘记了在他的代码中管理访问过的顶点。更准确地说,他编写了以下代码:
1: $当前 \leftarrow \{start\_vertex\}$ 2: while $current \ne$ 所有顶点的集合 3: $找到\leftarrow \{\}$ 4: 对于 $v$ 在 $current$ 中 5:对于与$v$相邻的每个$u$ 6: $找到 \leftarrow 找到 \cup \{u\}$ 7:$当前\找到左箭头$
您可能会注意到,对于某些图表,远藤先生的程序不会停止,因为它会无限运行。请注意,这并不一定意味着程序无法在有限步骤内探索所有顶点。有关更多详细信息,请参见下面的示例 2。您的任务是编写一个程序,确定 Endo 先生的程序是否会在给定图形的有限步内停止,以便向他指出错误。另外,如果程序是有限的,则计算程序停止所需的最小循环迭代次数。
输入
输入由单个测试用例组成,格式如下。
$N$ $M$ $U_{1}$ $V_{1}$ $\vdots$ $U_{M}$ $V_{M}$
第一行由两个整数 $N$ ($2 \le N \le 100{,}000$) 和 $M$ ($1 \le M \le 100{,}000$) 组成,其中 $N$ 分别是给定无向图中的顶点数,$M$ 是边数。 接下来的$M$行中的第$i$行由两个整数$U_{i}$和$V_{i}$组成($1 \le U_{i}, V_{i} \le N$),这意味着顶点$U_{i}$和$V_{i}$在给定图中是相邻的。顶点1是起始顶点,即伪代码中的$start\_vertex$。 您可以假设给定的图也满足以下条件。
- 该图没有自环,即 $U_{i} \ne V_{i}$ 对于所有 $1 \le i \le M$。
- 该图没有多边边,即 $\{U_{i}, V_{i}\} \ne \{U_{j}, V_{j}\} $ 对于所有 $1 \le i < j \le M$。
- 该图是连通的,即对于所有顶点 $1 \le U, V \le N$,至少有一条从 $U$ 到 $V$ 的路径(反之亦然)。
输出
如果 Endo 先生错误的 BFS 代码对于给定的输入图不能在有限步内停止,则在一行中打印 -1。否则,打印停止所需的最小循环迭代次数。
示例输入 1
3 3 1 2 1 3 2 3
样本输入 1 的输出
2
示例输入 2
4 3 1 2 2 3 3 4
样本输入 2 的输出
-1
$current$ 的转换为 $\{1\} \rightarrow \{2\} \rightarrow \{1, 3\} \rightarrow \{2, 4\} \rightarrow \{1, 3\} \rightarrow \{2, 4\} \rightarrow \cdots$。尽管Endo先生的程序将实现访问所有顶点(分3步),但是$current$永远不会成为与所有顶点相同的集合。
示例输入 3
4 4 1 2 2 3 3 4 4 1
样本输入 3 的输出
-1
示例输入 4
8 9 2 1 3 5 1 6 2 5 3 1 8 4 2 7 7 1 7 4
样本输入 4 的输出
3