题目描述

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。 このグラフの頂点には $1,\ 2,\ \dots,\ N$ の番号が付けられており、$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結びます。

以下の条件を満たすように辺を $0$ 本以上取り除いたときの、グラフの連結成分の個数としてあり得る最小値を求めてください。

条件
$1\ \le\ a\ <\ b\ \le\ N$ を満たす任意の頂点の組 $(a,\ b)$ について、 頂点 $a$ と頂点 $b$ が同じ連結成分に属するならば、頂点 $a$ と頂点 $b$ を直接結ぶ辺が存在する。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

答えを出力せよ。

题目大意

给定一个 $N$ 个节点 $M$ 条边的无向图，要求通过删去若干条边（可以不删），使得每个连通块都是完全图。求最少分成多少个连通块。

3 2
1 2
1 3

2

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\ <\ B_i\ \le\ N$
• $i\ \neq\ j$ ならば $(A_i,\ B_i)\ \neq\ (A_j,\ B_j)$

Sample Explanation 1

辺を取り除かないと、 $(2,\ 3)$ の組が条件を満たしません。 どちらかの辺を取り除くと、頂点 $2$ と頂点 $3$ が非連結になり、条件を満たします。