A5438. 二分图化
编程题
普及-
知识点
题目描述
给定一个包含 $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$ 的不同边对），则称该图为**简单图**。
---
### 什么是“二分图”？
如果能够将图中每个顶点染成黑色或白色，使得：
- 对于每一条边，连接的两个顶点颜色不同，
则称该图为**二分图**。
图中包含顶点 $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$
> $N\ M$
> $u_1\ v_1$
> $u_2\ v_2$
> $\vdots$
> $u_M\ v_M$
输出格式
输出一个整数，表示最少需要删除多少条边，才能使图成为二分图。
输入输出样例
输入 #1
5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5
输出 #1
2
输入 #2
2 1 1 2
输出 #2
0
输入 #3
10 20 5 9 1 4 3 8 1 6 4 10 5 7 5 6 3 7 3 6 5 10 1 3 3 4 6 7 1 2 4 7 1 5 1 9 9 10 4 5 8 9
输出 #3
5
说明/提示
### 样例 1 说明
可以通过删除两条边使图变为二分图：
例如删除连接顶点 $1$ 和 $3$ 的边，以及连接顶点 $3$ 和 $5$ 的边。
如果只删除一条边或不删除边，都无法使图成为二分图。
因此答案为
---
### 样例 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$）
- 图保证是简单图
- 所有输入均为整数
可以通过删除两条边使图变为二分图：
例如删除连接顶点 $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$）
- 图保证是简单图
- 所有输入均为整数