0x60图论（0x66 Tarjan算法与无向图连通性）例题3：圆桌骑士

题目描述

国王要在圆桌上召开骑士会议，但有若干对骑士之间互相憎恨。

有如下要求：

1、相互憎恨的两个骑士不能坐在相邻的两个位置。

2、为了让投票表决议题时都能有结果（不平票），出席会议的骑士数必须是奇数。

3、参与会议的骑士数量不能只有 $1$ 名。

如果有某个骑士无法出席任何会议，则国王会为了世界和平把他踢出骑士团。

现在给定骑士总数 $n$，以及 $m$ 对相互憎恨的关系，求至少要踢掉多少个骑士。

输入格式

多组数据，每组数据描述如下：

第一行两个整数 $n$ $m$ $(1 \le n \le 1000, m \le 10^6)$。

下来 $m$ 行，每行两个整数 $a$ $b$，表示骑士 $a$ 和骑士 $b$ 相互憎恨。

当遇到某行为 $0$ $0$ 时表示输入终止。

输出格式

每个测试用例输出一个整数，表示结果。每个结果占一行。

输入输出样例

输入 #1

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

输出 #1

2