Description

小哼今天和小伙伴们一起去游乐场玩，终于可以坐上梦寐以求的过山车了。过山车的每一排只有两个座位，为了安全起见，是每个女生必须和一个男生做一排。但是，每个人都希望与自己认识的人坐在一起。如何安排才可以让更多认识的男生和女生坐在一起呢？

Input Format

输入第一行为两个整数n,m。n表示有n个人（其中前1～n/2号为女生，n/2+1~n号为男生）,m表示有m个关系。(1 < n,m < 10)

后面m行，每行两个数a,b，表示a和b互相认识。

Output Format

输出最大匹配个数（最多有几对男生女生可以坐在一起）

6 5
1 4
1 5
2 5
2 6
3 4​

3​

Hint

对于样例的解释：

1号女生和5号男生

2号女生和6号男生

3号女生和4号男生

一共三组（全部）匹配成功，所以最大匹配数是3。

Source

图论 二分图