Anadi and Domino

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 7$$$, $$$0 \leq m \leq \frac{n\cdot(n-1)}{2}$$$) — the number of vertices and the number of edges in the graph.

The next $$$m$$$ lines contain two integers each. Integers in the $$$i$$$-th line are $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$) and denote that there is an edge which connects vertices $$$a_i$$$ and $$$b_i$$$.

The graph might be disconnected. It's however guaranteed that the graph doesn't contain any self-loops, and that there is at most one edge between any pair of vertices.

Output:

Output one integer which denotes the maximum number of dominoes which Anadi can place on the edges of the graph.

Sample Input:

4 4
1 2
2 3
3 4
4 1

Sample Output:

4

Sample Input:

7 0

Sample Output:

0

Sample Input:

3 1
1 3

Sample Output:

1

Sample Input:

7 21
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

Sample Output:

16

Note:

Here is an illustration of Anadi's graph from the first sample test:

And here is one of the ways to place a domino on each of its edges:

Note that each vertex is faced by the halves of dominoes with the same number of dots. For instance, all halves directed toward vertex $$$1$$$ have three dots.