Bob has made a list of $N$ new year's resolutions, numbered from $1$ to $N$. Upon closer inspection, however, he notices some resolutions contradict each other!

As a result, he has made a list of $M$ restrictions, each of which is a pair $(r_i,r_j)$ stating that if Bob fulfills the $r_i$-th resolution, he cannot fulfill the $r_j$-th resolution, and vice versa.

Wanting to have as many resolutions as possible, can you determine the maximum number of resolutions he can keep in his original list?

Constraints

For this problem, you will be required to pass all the samples in order to receive any points. However, you are NOT required to pass all previous subtasks to receive points for a specific subtask.

$2\le N\le 18$

$0\le M\le \frac{N(N-1)}{2}$

$1\le r_i,r_j\le N$

$r_i\ne r_j$

Each restriction will only be stated once. Note that the restriction $(r_i,r_j)$ is the same as the restriction $(r_j,r_i)$.

Subtask 1 [5/15]

$0\le M\le 2$

Subtask 2 [7/15]

$2\le N\le 10$

Subtask 3 [3/15]

No additional constraints.

Input Specification

The first line will contain $2$ integers $N$ and $M$.

The next $M$ lines will contain $2$ integers $r_i$ and $r_j$.

Output Specification

Output one integer on one line, the maximum number of resolutions he can keep in his original list.

Sample Input

4 2
1 2
3 2

Sample Output

3

Explanation

Bob should remove resolution $2$ and keep the rest of the resolutions.