配点 : $600$ 点

問題文

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

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

条件 $1 \le a < b \le N$ を満たす任意の頂点の組 $(a, b)$ について、 頂点 $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$

出力

答えを出力せよ。

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