题目描述

国王有时会在圆桌上召开骑士会议。

由于骑士的数量很多，所以每个骑士都前来参与会议的情况非常少见。

通常只会有一部分骑士前来参与会议，而其余的骑士则忙着在全国各地做英勇事迹。

骑士们都争强好胜，好勇斗狠，经常在会议中大打出手，影响会议的正常进行。

现在已知有若干对骑士之间互相憎恨。

为了会议能够顺利的召开，每次开会都必须满足如下要求：

$\red {1}$、相互憎恨的两个骑士不能坐在相邻的两个位置。

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

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

如果前来参加会议的骑士，不能同时满足以上三个要求，会议会被取消。

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

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

输入格式

输入包含多组测试用例。

对于每个用例，第一行包含两个整数 $\red {n}$ 和 $\red {m}$。

接下来 $\red {m}$ 行，每行包含两个整数 $\red {a}$ 和 $\red {b}$，表示骑士 $\red {a}$ 和骑士 $\red {b}$ 相互憎恨。

当遇到某行为$\red {0 ~0}$时表示输入终止。

输出格式

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

每个结果占一行。

样例

输入样例

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

输出样例

2

提示

$\red {n≤1000,m≤10^6}$