$\colorbox{green}{\color{white}Score : 600 points}$

问题陈述

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

在移除零条或多条边后，找到图中可能的最小连通分量数量，以满足以下条件：

条件：
对于每一对顶点$(a, b)$，满足$1 \le a < b \le N$，如果顶点$a$和$b$属于同一个连通分量，那么存在一条直接连接顶点$a$和$b$的边。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

Given is a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1, 2, \dots, N$, and the $i$-th edge connects Vertices $A_i$ and $B_i$.

Find the minimum possible number of connected components in the graph after removing zero or more edges so that the following condition will be satisfied:

Condition:
For every pair of vertices $(a, b)$ such that $1 \le a < b \le N$, if Vertices $a$ and $b$ belong to the same connected component, there is an edge that directly connects Vertices $a$ and $b$.

Constraints

• All values in input are integers.
• $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)$ for $i \neq j$.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

Output

Print the answer.

Sample Input 1

3 2
1 2
1 3

Sample Output 1

2

Without removing edges, the pair $(2, 3)$ violates the condition. Removing one of the edges disconnects Vertices $2$ and $3$, satisfying the condition.

Sample Input 2

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

Sample Output 2

1

Sample Input 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

Sample Output 3

5

Sample Input 4

18 0

Sample Output 4

18