F - Close Group Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 1

3 2
1 2
1 3

出力例 1

2

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

入力例 2

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

出力例 2

1

入力例 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

出力例 3

5

入力例 4

18 0

出力例 4

18

Score : 600 points

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