题目描述

给定一个无向图，有 $N$ 个顶点和 $M$ 条边。满足条件 $N-1≤M≤N$，且图是连通的。这个图中不存在自环或重复的边。

顶点从 $1$ 到 $N$ 编号，边从 $1$ 到 $M$ 编号。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

每个顶点的颜色可以是白色或黑色。初始状态下，所有顶点都是白色。Snuke 试图通过执行以下操作若干次将所有顶点变为黑色：

• 选择一对颜色相同的相邻顶点，并反转这两个顶点的颜色。也就是说，如果两个顶点都是白色，则将它们变为黑色，反之亦然。

确定是否能够将所有顶点变为黑色。如果答案是正的，则找出实现目标所需进行操作的最小次数。

约束条件

• $2≤N≤10^5$
• $N-1≤M≤N$
• $1≤a_i,b_i≤N$
• 给定图中不存在自环或重复的边。
• 给定图是连通的。

分段得分

• 在价值 $1500$ 分的测试集中，$M=N-1$。

输入

输入的格式如下，从标准输入给出：

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$

输出

如果能够将所有顶点变为黑色，则打印实现目标所需进行操作的最小次数。否则，打印 -1。

示例输入1

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

示例输出1

5

例如，可以按照下图所示的方式执行操作：

示例输入2

3 2
1 2
2 3

示例输出2

-1

无法将所有顶点变为黑色。

示例输入3

4 4
1 2
2 3
3 4
4 1

示例输出3

2

这个案例不包含在分段得分的测试集中。

示例输入4

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

示例输出4

7

这个案例不包含在分段得分的测试集中。