A83509.二分图化

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。
图中包含顶点 $1, 2, \ldots, N$，第 $i$ 条边 $(1 \le i \le M)$ 连接顶点 $u_i$ 和 $v_i$。

你可以进行以下操作若干次（可以为 0 次）：

• 选择一条尚未被删除的边，将其删除。

你的目标是让图变成二分图。
请输出最少需要进行多少次操作，才能使删除操作后的图成为二分图。

---

什么是“简单图”？

若一个图没有自环（即不存在 $u_i = v_i$）且没有重边（不存在 $u_i = u_j$ 且 $v_i = v_j$ 的不同边对），则称该图为简单图。

---

什么是“二分图”？

如果能够将图中每个顶点染成黑色或白色，使得：

• 对于每一条边，连接的两个顶点颜色不同，

则称该图为二分图。

从标准输入读取：

$N\ M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

输出一个整数，表示最少需要删除多少条边，才能使图成为二分图。

样例 1 说明

可以通过删除两条边使图变为二分图：
例如删除连接顶点 $1$ 和 $3$ 的边，以及连接顶点 $3$ 和 $5$ 的边。

如果只删除一条边或不删除边，都无法使图成为二分图。
因此答案为 2。

---

样例 2 说明

该图本身就是二分图。
因此不需要进行任何操作，答案为 $0$。

---

数据范围

• $2 \le N \le 10$
• $1 \le M \le \dfrac{N(N-1)}{2}$
• $1 \le u_i < v_i \le N$（$1 \le i \le M$）
• 图保证是简单图
• 所有输入均为整数