#D. 收集宝石

    传统题 1000ms 256MiB

收集宝石

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

聪聪在玩冒险岛游戏,为了召唤法力更强大的神龙,他必须尽可能收集更多的魔法宝石,每颗宝石都有不同 的功效。不过在游戏里,几乎每一颗魔法宝石都会和另外一颗宝石相冲。相冲表示这两颗宝石不能同时拥有。

例如,宝石A和宝石B相冲,那么,你可以选择两颗宝石都不收集,也可以只收集宝石A或者只收集宝石B,但 不能同时拥有宝石A和宝石B。 现在给定了游戏里宝石的数量N(2≤N≤100),宝石从1到N依次编号,并给出M对(2≤M≤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。

格式

输入

image

输出

image

样例

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

周六测试

未参加
状态
已结束
规则
ACM/ICPC
题目
5
开始于
2024-10-19 9:00
结束于
2024-10-19 19:00
持续时间
10 小时
主持人
参赛人数
11