← 返回题目列表

Codeforces · 216/B

B. 组建团队

中文机器翻译题面 查看原题

有一天,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