AT_abc427_c.[ABC427C] Bipartize

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

你可以进行如下操作任意次（也可以不进行操作）：

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

你的目标是通过上述操作使图变为二分图。请你求出最少需要进行多少次操作，才能使经过操作后的图变为二分图。

什么是简单图？简单图指的是没有自环（即不存在 $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\le10$
• $1\le M\le\dfrac{N(N-1)}2$
• $1\le u_i < v_i \le N\ (1\le i\le M)$
• 给定的图是简单图。
• 所有输入值均为整数。

由 ChatGPT 5 翻译