← 返回题目列表

AtCoder · agc004_f

F. 纳森

中文机器翻译题面 查看原题

分数: 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

这种情况不包含在部分分数的测试集中。