#P12904. [AGC004F] Namori

    ID: 12087 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-基环树断环成链线性不定方程不变量分析奇偶性分析中位数最小化绝对偏差和深度优先搜索

[AGC004F] Namori

题目描述

给定一个由 NN 个顶点和 MM 条边构成的无向图。其中,N−1≤M≤NN-1 \le M \le N,且图连通。此外,图中没有自环和重边。

顶点编号为 11 到 NN,边编号为 11 到 MM。边 ii 连接顶点 aia_i 和 bib_i。

每个顶点可以被染成白色或黑色。初始时,所有顶点都是白色的。你需要通过进行以下操作若干次,将所有顶点变为黑色:

  • 选择一对相邻(位于同一条边的两端)的同色顶点,将它们颜色同时反转。即,若均为白色则变为黑色,若均为黑色则变为白色。

请判断是否可以将所有顶点变为黑色,如果可以,输出所需的最小操作次数;否则输出 -1。

输入格式

输入格式如下:

N N M M
a1 a_1 b1 b_1
a2 a_2 b2 b_2
: :
aM a_M bM b_M

输出格式

如果可以将所有顶点变为黑色,输出所需的最小操作次数;否则输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

5

输入输出样例 #2

输入 #2

3 2
1 2
2 3

输出 #2

-1

输入输出样例 #3

输入 #3

4 4
1 2
2 3
3 4
4 1

输出 #3

2

输入输出样例 #4

输入 #4

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

输出 #4

7

说明/提示

数据范围与约定

  • 2≤N≤1052 \le N \le 10^5
  • N−1≤M≤NN-1 \le M \le N
  • 1≤ai,bi≤N1 \le a_i, b_i \le N
  • 图中没有自环和重边。
  • 图是连通的。

部分分

  • 在 15001500 分的测试数据中,满足 M=N−1M = N-1。

样例解释 #1

例如,可以按照图示的方式进行操作。

样例解释 #2

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

样例解释 #3

此样例不被包含在部分分的测试数据中。

样例解释 #4

此样例不被包含在部分分的测试数据中。