TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3628
  • 题目
  • P3628部落卫队
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    原始部落中的居民为了争夺资源,常发生冲突。几乎每个居民都有仇敌。
    酋长为了组织一个部落卫队,希望从部落居民中选出最多的居民入伍,并保证队伍中任何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