F - 闭合群

分值：$600$ 分

问题描述

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

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

条件：
对于每一对顶点 $(a, b)$，满足 $1 \le a < b \le N$，如果顶点 $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$

输出

输出答案。

3 2
1 2
1 3

2

没有移除边的情况下，顶点对 $(2, 3)$ 不满足条件。 移除其中一条边会使顶点 $2$ 和 $3$ 之间断开连接，从而满足条件。

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

1

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

5

18 0

18