题目描述

作为一名骑士是一个非常吸引人的职业：寻找圣杯、拯救处于困境中的少女、与其他骑士共饮都是有趣的事情。因此，近年来，亚瑟王的王国骑士数量空前增长也就不足为奇了。现在骑士太多了，很少能有一次圆桌骑士全部同时来到卡美洛并围坐在圆桌旁的情况；通常只有一小部分骑士在场，而其余骑士则在王国各地忙于英勇事迹。

骑士们在讨论时很容易过度兴奋——尤其是在喝了几杯之后。在一些不幸的事件发生后，亚瑟王要求著名的巫师梅林确保未来骑士之间不会发生争斗。经过仔细研究，梅林发现只有按照以下两条规则安排座位才能防止争斗：

1. 骑士的座位安排必须满足：两个互相憎恨的骑士不能坐在相邻的位置。（梅林有一份清单，记录了谁憎恨谁。）骑士们围坐在圆桌旁，因此每个骑士恰好有两个邻居。
2. 围坐在桌旁的骑士人数必须是奇数。这样可以确保如果骑士们无法达成一致，可以通过投票解决问题。（如果骑士人数是偶数，可能会出现“赞成”和“反对”票数相同的情况，争论会继续。）

梅林只有在满足这两条规则的情况下才会让骑士们入座，否则他会取消会议。（如果只有一名骑士到场，会议也会取消，因为一个人无法围坐在桌旁。）梅林意识到，这意味着有些骑士可能无法成为任何符合这些规则的座位安排的一部分，这些骑士将永远无法坐在圆桌旁（例如，一个骑士憎恨所有其他骑士，但还有许多其他可能的原因）。如果一个骑士不能坐在圆桌旁，那么他就不能成为圆桌骑士团的成员，必须被驱逐出骑士团。这些骑士将被调到一个不那么 prestigious 的骑士团，比如方桌骑士团、八角桌骑士团或香蕉形桌骑士团。

为了帮助梅林，你需要编写一个程序，确定必须驱逐的骑士数量。

输入格式

输入包含多个测试用例块。每个测试用例的第一行是两个整数 1 ≤ n ≤ 1000 和 1 ≤ m ≤ 1000000，其中 n 是骑士的数量，m 是憎恨关系的数量。接下来的 m 行描述哪些骑士互相憎恨，每行包含两个整数 k1 和 k2，表示骑士 k1 和骑士 k2 互相憎恨（k1 和 k2 的取值范围是 1 到 n）。

输入以 n = m = 0 的块结束。

输出格式

对于每个测试用例，输出一行一个整数：必须驱逐的骑士数量。

示例输入

5 5
1 4
1 5
2 5
3 4
4 5
0 0

示例输出

2

提示

输入文件非常大，建议使用 scanf 以避免超时。

来源

Central Europe 2005