构造 2-正则图

题目描述

育华学校信息学社团正在研究图论相关的趣味问题。现有一个简单无向图 $G$，包含 $N$ 个顶点（对应校园里的 $N$ 个标志性建筑，编号 $1, 2, \dots, N$ ）和 $M$ 条边（代表建筑之间的通道 ）。

社团成员可以重复进行以下两种操作任意次数：

• 操作一：向图 $G$ 中添加一条无向边（新增一条建筑间通道 ）。
• 操作二：从图 $G$ 中移除一条无向边（拆除一条建筑间通道 ）。

目标是通过最少的操作次数，将图 $G$ 转变为一个所有顶点的度数都为 2 的简单无向图（即每个建筑恰好连接两条通道，形成特定的环路结构 ）。请你帮忙计算达成目标所需的最小操作次数。

这里的“简单无向图”指没有自环（同一建筑到自身的通道 ）和多重边（同一对建筑间有多条通道 ）的无向图。

输入格式

输入从标准输入按以下格式给出，对应图 $G$ 的信息：

N M  
A_1 B_1  
A_2 B_2  
...  
A_M B_M  

其中，$N$ 是顶点数量，$M$ 是边数量，接下来 $M$ 行每行的 $A_i$ 和 $B_i$ 表示连接顶点 $A_i$ 和 $B_i$ 的无向边（建筑间通道 ）。

输出格式

输出一个整数，即把图 $G$ 转变为所有顶点度数均为 2 的简单无向图所需的最小操作次数。

样例说明

样例输入 1

5 4  
1 2  
1 5  
2 4  
4 5  

样例输出 1

3  

解释

可通过以下 3 次操作达成目标：

1. 添加连接顶点 2 和 3 的边（新增建筑 2 与 3 间通道 ）。
2. 移除连接顶点 2 和 4 的边（拆除建筑 2 与 4 间通道 ）。
3. 添加连接顶点 3 和 4 的边（新增建筑 3 与 4 间通道 ）。
   操作后所有顶点度数变为 2 。

样例输入 2

3 0  

样例输出 2

3  

解释

初始没有边，要让 3 个顶点度数都为 2 ，需构建一个三角形（3 条边 ），所以要进行 3 次添加边操作。

样例输入 3

6 8  
1 2  
2 3  
3 4  
3 6  
4 5  
4 6  
5 6  
1 5  

样例输出 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  

样例5

见选手文件中的 regular/regular5.in 与 regular/regular5.ans。

数据范围

• 顶点数量约束：$3 \leq N \leq 8$（对应校园里最多 8 个标志性建筑 ）。
• 边数量约束：$0 \leq M \leq \frac{N(N - 1)}{2}$（简单无向图最多边数 ）。
• 输入的图 $G$ 是简单无向图，所有输入值为整数。