← 返回题目列表

AtCoder · abc412_d

G. 制作 2-正则图

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

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