问题陈述

给定一个简单的无向图，其中有 $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$
• 对于任意 $i \\neq j$，$(A_i, B_i) \\neq (A_j, B_j)$。

输入

输入以以下格式从标准输入给出:

$N$ $M$ $A_1$ $B_1$ $\\vdots$ $A_M$ $B_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