分数: 425 点
问题陈述
有一个简单的无向图 G 与 N 顶点和 M 边缘。顶点已编号 1, 2, \ldots, N,以及 i-th 边是连接顶点的无向边 A_i 和 B_i.
您可以按任意顺序和任意次数重复以下两个操作:
- 添加一条无向边 G
- 删除一条无向边 G
查找要进行的最少操作数 G 一个简单的无向图,其中所有顶点都有度数 2.
什么是简单无向图?
简单无向图是指没有自环、没有多边的无向图。
约束
- 3 \leq N \leq 8
- 0 \leq M \leq \frac{N(N-1)}{2}
- 图表 输入中给出的 G 是一个简单的无向图。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 \vdots A_M B_M
输出
输出答案。
示例输入 1
5 4 1 2 1 5 2 4 4 5
示例输出 1
3
例如,以下三个操作使 G 一个简单的无向图,其中所有顶点都有度数 2.
- 添加连接顶点的边 2 和 3.
- 删除连接顶点的边 2 和 4.
- 添加连接顶点的边 3 和 4.
示例输入 2
3 0
示例输出 2
3
示例输入 3
6 8 1 4 1 5 2 3 2 6 3 4 3 6 4 5 4 6
示例输出 3
2
示例输入 4
8 21 1 4 5 7 8 4 3 4 2 5 8 1 5 1 2 8 2 1 2 4 3 1 6 7 5 8 2 7 6 8 5 4 3 8 7 3 7 8 5 3 7 4
示例输出 4
13