MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

---

### 问题描述

Endo 先生希望编写一段实现广度优先搜索（BFS）的代码，BFS 是一种用于遍历无向图上所有顶点的搜索算法。BFS 伪代码示例如下：

> 1: $current \\leftarrow \\{start\\_vertex\\}$ 2: $visited \\leftarrow current$ 3: while $visited \\ne$ 所有顶点的集合 4: $found \\leftarrow \\{\\}$ 5: 对于 $current$ 中的每个顶点 $v$ 6: 对于与 $v$ 相邻的每个顶点 $u$ 7: $found \\leftarrow found \\cup \\{u\\}$ 8: $current \\leftarrow found \\setminus visited$ 9: $visited \\leftarrow visited \\cup found$

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

> 1: $current \\leftarrow \\{start\\_vertex\\}$ 2: 当 $current \\ne$ 所有顶点的集合时 3: $found \\leftarrow \\{\\}$ 4: 对于 $current$ 中的每个顶点 $v$ 5: 对于与 $v$ 相邻的每个顶点 $u$ 6: $found \\leftarrow found \\cup \\{u\\}$ 7: $current \\leftarrow found$

你可能会发现，对于某些图形，Endo 先生的程序将不会停止，因为它会无限运行。但这并不一定意味着该程序无法在有限步骤内遍历所有顶点。请参阅下面的示例 2 以了解更多详情。你的任务是编写一个程序，判断给定图形中 Endo 先生的程序是否能够在有限步骤内停止，并指出代码中的错误。另外，如果程序是有限的，计算停止所需的最小循环迭代次数。

---

### 输入

输入包含一个单独的测试用例，格式如下所示。

> $N$ $M$ $U_{1}$ $V_{1}$ $\cdots$ $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$（或从 $V$ 到 $U$）的路径。

---

### 输出

如果 Endo 先生错误的 BFS 代码在给定输入图形中无法在有限步骤内停止，则在一行中打印 -1。否则，打印停止所需的最小循环迭代次数。

---

### 示例输入 1

```plain
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