题目描述

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

找到在删除零条或更多边后，使得满足以下条件的图中可能的最少连通块数量：

对于每一对顶点(a, b)，其中$1 \le a < b \le N$，如果顶点a和b属于相同的连通块，那么存在一条直接连接顶点a和b的边。

约束条件

所有输入值都是整数。

$1 \le N \le 18$

$0 \le M \le \frac{N(N - 1)}{2}$

$1 \le A_i < B_i \le N$

$(A_i, B_i) \neq (A_j, B_j)$，对于$i \neq j$。

输入

第一行两个整数 $N,M$

接下来$M$行，表示一条边

输出

输出答案。

样例输入 1

3 2
1 2
1 3

样例输出 1

2

在不移除边的情况下，对(2, 3)这一对违反了条件。移除其中一条边会断开顶点2和3的连接，从而满足条件。

样例输入 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

样例输出 2

1

样例输入 3

10 11
9 10
2 10
8 9
3 4
5 8
1 8
5 6
2 5
3 6
6 9
1 9

样例输出 3

5

样例输入 4

18 0

样例输出 4

18