紧密集团

题目描述

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

在满足以下条件的前提下，从图中删去 $0$ 条以上的边时，求图的连通分量个数可能的最小值。

条件

对于任意满足 $1 \le a \lt b \le N$ 的顶点对 $(a, b)$，如果顶点 $a$ 和顶点 $b$ 属于同一连通分量，则存在直接连接顶点 $a$ 和顶点 $b$ 的边。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• 输入均为整数
• $1 \le N \le 18$
• $0 \le M \le \frac{N(N - 1)}{2}$
• $1 \le A_i \lt B_i \le N$
• 若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$