题目描述

有一个包含 $N$ 个顶点、$M$ 条边的简单无向图 $G$。顶点编号为 $1, 2, \ldots, N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

你可以按任意顺序、任意次数重复以下两种操作：

• 向 $G$ 中添加一条无向边。
• 从 $G$ 中删除一条无向边。

请你求出，将 $G$ 变为所有顶点的度数都为 $2$ 的简单无向图所需操作次数的最小值。

简单无向图指的是没有自环和重边的无向图。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

输出格式

请输出答案。

样例

5 4
1 2
1 5
2 4
4 5

3

3 0

3

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

2

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

13

提示

样例1解释

例如，可以通过如下方式，在 $3$ 次操作内将 $G$ 变为所有顶点度数为 $2$ 的简单无向图：

• 添加一条连接顶点 $2$ 和顶点 $3$ 的边。
• 删除一条连接顶点 $2$ 和顶点 $4$ 的边。
• 添加一条连接顶点 $3$ 和顶点 $4$ 的边。

数据范围

• $3 \leq N \leq 8$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• 输入给出的图 $G$ 是简单无向图
• 输入的所有数值均为整数