P3628部落卫队 | |
|
问题描述
原始部落中的居民为了争夺资源,常发生冲突。几乎每个居民都有仇敌。
酋长为了组织一个部落卫队,希望从部落居民中选出最多的居民入伍,并保证队伍中任何2个人都不是仇敌。
根据给定的居民间的仇敌关系,编程计算出部落卫队的最佳方案,输出最佳方案的人数。
输入格式
第1行2个整数n,m表示部落中居民个数,居民中有m个仇敌关系。居民编号1,2,...,n。
接下来m行,每行2个整数u,v表示居民u和v是仇敌。
输出格式
一个整数,最佳方案的人数
样例输入
7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6
样例输出
3
提示
2<=n<=100
1<=m<=3000