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.

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.

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$.

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

见题面 Input 部分

见题面 Output 部分