分数: 2200 点
问题陈述
给你一个无向图 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
这种情况不包含在部分分数的测试集中。
