#P3852. [TJOI2007] 小朋友

[TJOI2007] 小朋友

题目背景

幼儿园里有N个小朋友,老师要从中选出来一部分做丢手绢的游戏,可是老师没有想到这么小的孩子里面有些人之间还有矛盾。老师想找出尽量多的小朋友去玩游戏,但是又很头疼,他不想看到找出来玩游戏的小朋友里面还有任何两个人之间存在着矛盾。如果告诉你小朋友之间存在的M对矛盾关系,你能否帮助幼儿园老师计算出他最多可以选出多少个小朋友来做这个丢手绢的游戏?

题目描述

关于矛盾限制的说明:

如果我们把存在着矛盾的两个小朋友看作是无向图中相连的两个点,那么题目中的数据保证M对矛盾所构成的图中不会有超过3个点的环。(图1符合要求,图2则不符合)

输入格式

输入文件的第一行是用空格隔开的两个整数N和M,表示一共有N个小朋友,这些小朋友之间有M对矛盾关系。接下来的M行,每行将有一对整数a和b(用空格隔开),表示小朋友a与小朋友b有矛盾。(小朋友的编号都是从1开始的)

输出格式

输出一行,包含一个整数,即幼儿园老师最多可以选出来做游戏的人数。

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

提示

幼儿园有6个小朋友,矛盾关系中1 - 2 - 3组成一个环,3 - 4 - 5组成一个环,因此只能在这两个环中分别选一个小朋友,并且不能选择3号小朋友。

对于20%的数据,1 ≤ N ≤ 20

对于40%的数据,1 ≤ N ≤ 50

对于100%的数据,1 ≤ N ≤ 200

对于100%的数据都符合题目中所描述的矛盾限制关系。