90058 - 收集宝石

通过次数

2

提交次数

2

时间限制 : 1 秒
内存限制 : 128 MB

聪聪在玩冒险岛游戏,为了召唤法力更强大的神龙,他必须尽可能收集更多的魔法宝石,每颗宝石都有不同的功效,不过在游戏里,几乎每一颗魔法宝石都会和另外一颗宝石相冲。相冲表示这两颗宝石不能同时拥有。
例如,宝石A和宝石B相冲,那么,你可以选择两颗宝石都不收集,也可以只收集宝石A或者只收集宝石B,但不能同时拥有宝石A和宝石B。

现在给定了游戏里宝石的数量n(2 \le n \le 100),宝石从1到n依次编号,并给出m(2 \le m \le 2000)相冲的宝石编号,请帮聪聪计算出最多能够收集到多少颗宝石。
例如:n=6,m=8时,6颗宝石的编号分别为1、2、3、4、5、6,其中有8对相冲的宝石,对应编号如下:

1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6

这表示宝石1和宝石2相冲,宝石2和宝石3、4、5、6都相冲,宝石3和宝石4相冲,宝石4和宝石5相冲,宝石5和宝石6相冲。

有三个方案收集到的宝石数量最多:(1 3 5)、(1 3 6)、(1 4 6),这些方案里,最多收集到的宝石数量都是3,所以程序输出3。

输入

第一行输入两个正整数nm(2 \le n \le 100,2 \le m \le 2000),分别表示游戏里的宝石数量和m对相冲的宝石,两个正整数之间用一个空格隔开。
接下来输入m行,每行两个正整数,分别表示相冲的两颗宝石的编号,两个整数之间用一个空格隔开。

输出

输出一个整数,表示聪聪在游戏里最多能够收集到的宝石数量。

样例

输入

6 8
1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6

输出

3

来源

蓝桥杯测评