TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3628
  • Problem
  • P3628部落卫队
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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


    根据给定的居民间的仇敌关系,编程计算出部落卫队的最佳方案,输出最佳方案的人数。

    Input Format

    第1行2个整数n,m表示部落中居民个数,居民中有m个仇敌关系。居民编号1,2,...,n。
    接下来m行,每行2个整数u,v表示居民u和v是仇敌。

    Output Format

    一个整数,最佳方案的人数

    Sample Input

    7 10
    1 2
    1 4
    2 4
    2 3
    2 5
    2 6
    3 5
    3 6
    4 5
    5 6

    Sample Output

    3

    Hint

    2<=n<=100
    1<=m<=3000