阿纳迪有一组多米诺骨牌。每张多米诺骨牌都有两部分,每一部分都包含一些点。对于每个 $$$a$$$ 和 $$$b$$$ 使得 $$$1 \leq a \leq b \leq 6$$$,恰好存在一张多米诺骨牌,其一半上有 $$$a$$$ 点,另一半上有 $$$b$$$ 点。该套装包含 $$$21$$$ 多米诺骨牌。这是他的集合的精确说明:
此外,Anadi 有一个无向图,没有自环和多重边。他想选择一些多米诺骨牌并将它们放置在该图的边缘上。每种类型他最多可以使用一张多米诺骨牌。每条边最多可以容纳一张多米诺骨牌。没有必要在图的每条边上都放置多米诺骨牌。
将多米诺骨牌放在边缘时,他也会选择其方向。换句话说,任何放置的多米诺骨牌的一半必须指向边缘的一个端点,另一半必须指向另一个端点。有一个问题:如果多米诺骨牌的多半都指向同一个顶点,那么每一半都必须包含相同数量的点。
阿纳迪最多可以在他的图的边缘放置多少张多米诺骨牌?
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 7$$$, $$$0 \leq m \leq \frac{n\cdot(n-1)}{2}$$$) — 图中的顶点数和边数。
接下来的 $$$m$$$ 行每行包含两个整数。第 $$$i$$$ 行中的整数是 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$),表示存在一条连接顶点 $$$a_i$$$ 和 $$$b_i$$$ 的边。
该图可能已断开连接。然而,可以保证该图不包含任何自环,并且任何一对顶点之间最多有一条边。
输出
输出一个整数,表示 Anadi 可以在图的边缘放置的多米诺骨牌的最大数量。
示例
输入 #1
4 4 1 2 2 3 3 4 4 1
输出 #1
4
输入 #2
7 0
输出 #2
0
输入 #3
3 1 1 3
输出 #3
1
输入#4
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
输出#4
16
注意
这是第一个示例测试中 Anadi 图表的说明:
这是在多米诺骨牌的每个边缘上放置多米诺骨牌的方法之一:
请注意,每个顶点都面临着具有相同点数的多米诺骨牌的一半。例如,指向顶点 $$$1$$$ 的所有半部分都有三个点。