← 返回题目列表

AtCoder · abc427_c

E. 两党

中文机器翻译题面 查看原题


分数: 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