有一天,n 个学生来到体育场。他们想要踢足球,为此他们需要分成几队,每队的人数必须相等。
我们知道这群人有宿敌。每个学生最多有两个宿敌。此外,如果学生A是学生B的大敌,那么学生B就是学生A的大敌。
学生们想要分开,这样一支队伍中就不会出现两个宿敌。如果无法按照要求的方式分开,一些学生将不得不坐在板凳上。
确定您必须派到替补席上的最少学生人数,以便以所描述的方式组成两队并最后开始比赛。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100)——对应的学生人数和宿敌对数。
接下来的m行描述了学生之间的敌意。每个敌意被描述为两个数字ai和bi(1≤ai,bi≤n,ai≠bi)——彼此敌对的学生的索引。每个敌意在列表中只出现一次。保证每个学生的大敌不超过两个。
您可以考虑以某种方式使用从 1 到 n 的不同整数进行索引的学生。
输出
打印一个整数——为了开始比赛,你必须派到替补席上的最少学生人数。
示例
输入 #1
5 4 1 2 2 4 5 3 1 4
输出 #1
1
输入 #2
6 2 1 4 3 4
输出 #2
0
输入 #3
6 6 1 2 2 3 3 1 4 5 5 6 6 4
输出 #3
2