该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

强哥在 Russland 上幼儿园期间，受洗成为了西歪教徒。西歪教徒会在自己的颈部挂一个项链，每位教徒的项链的图案都不一样。

强哥的项链的图案有 $N$ 朵小花（编号为 $1\sim N$）和连在这些小花之间的 $M$ 条丝线组成。每条丝线都有一半部分是蓝色的，另一半部分是白色的。

现在，强哥想要从这个图案中提取出他的信仰之环，假设这个环有 $k$ 朵小花，且每朵小花的编号分别是 $f_1,f_2,\cdots,f_k$，则必须满足以下要求：

1. $f_1,f_2,\cdots,f_k$ 互不相同。
2. $f_1 = 1$。
3. 对于 $1\le i< k$，满足花朵 $f_i$ 和花朵 $f_{i+1}$ 之间有丝线直接相连，且丝线连向 $f_i$ 那一端是蓝色的，连向 $f_{i+1}$ 那一端是白色的。
4. 花朵 $f_n$ 与 $f_1$ 也有丝线相连，且丝线连向 $f_n$ 那一端是蓝色的，连向 $f_{1}$ 那一端是白色的。

现在强哥想知道环上花朵的最少数量。

输入格式

第一行是空格分隔的两个整数： $N\ M$。

之后 $M$ 行，每行为一根丝线的两端：

• $a_1\ b_1$ ；
• $a_2\ b_2$ ；
• $\vdots$
• $a_M\ b_M$ 。

对于其中的第 $i$ 条丝线，连向 $a_i$ 的那一端是蓝色的，连向 $b_i$ 的那一端是白色的。

数据满足：

• $2 \leq N \leq 2 \times 10^5$ ；
• $1 \leq M \leq \min \big( \frac{N(N-1)}{2}, 2 \times 10^5 \big)$ ；
• 对 $i=1, ..., M$， 有 $1 \leq a_i, b_i \leq N$，且 $a_i \neq b_i$ ；
• 对任意的 $i \neq j$，都有 $(a_i, b_i) \neq (a_j, b_j)$ ，且 $(a_i, b_i) \neq (b_j, a_j)$ 。

输出格式

• 一个整数。环上花朵的最少数量。如果满足条件的环不存在，输出 $-1$ 。

3 3
1 2
2 3
3 1

3

3 2
1 2
2 3

-1

6 9
6 1
1 5
2 6
2 1
3 6
4 2
6 4
3 5
5 4

4