分数: 350 点
问题陈述
有一个简单的无向图 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).
什么是二分图?
二分图是可以将每个顶点着色为黑色或白色的图,并且满足以下条件:
- 对于每条边,由该边连接的两个顶点具有不同的颜色。
约束
- 2\le N\le10
- 1\le M\le\dfrac{N(N-1)}2
- 1\le u _ i\lt v _ i\le N\ (1\le i\le 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
您可以通过删除两条边来使图成为二分图:例如,连接顶点的边 1 和 3,以及连接顶点的边 3 和 5.
不可能通过执行一次或更少的操作使图成为二分图,因此打印 2.
示例输入 2
2 1 1 2
示例输出 2
0
该图从一开始就是二分图。 因此,需要执行的操作数为 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