[POI2005]Kos-Dicing

Dicing 是一种两人参与的游戏，在 Byteotia 非常流行，甚至有人专门成立了该游戏的俱乐部。俱乐部成员经常一起进行比赛，并评选出最优秀的选手。

现在有一位非常不走运的选手，他希望成为最优秀的选手。他已经知道了所有比赛的安排，想知道在最理想的比赛结果下，最终获胜场数最多的选手至少需要获胜多少场。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示参赛者人数和比赛场数。参赛者编号为 $1$ 至 $n$。

接下来 $m$ 行，每行包含两个整数，表示该场比赛的两名参赛者。同一对选手可能进行多场比赛。

输出格式

输出一个整数，表示在最理想的比赛结果下，最终获胜场数最多的选手至少需要获胜多少场。

样例输入

4 4
1 2
1 3
1 4
1 2

样例输出

1

数据范围

• $1\le n\le 10^4$；
• $0\le m\le 10^4$。

来源与许可

本题为 POI 2005 试题「Kos-Dicing」，题面与测试数据整理自 BZOJ 1532。

样例 1

输入

4 4
1 2
1 3
1 4
1 2

输出

1