#P0831. 部落冲突
部落冲突
题目描述
礼尚往来
在大陆上有个国家,国家之间经常相互进谏并献上国礼以表友好,但有些国家却不懂礼尚往来的江湖规矩,导致大陆上出现了许多敌对 关系。对于两个国家和,如果向进谏并献上国礼,且向进谏并回礼,和两个国家就是朋友;而如果向进谏并献上国礼,但未向进谏并回礼,和两个国家将成为敌人。
此外,大陆上还有一个潜规则:
- 一个国家的朋友的朋友就是这个国家的朋友。
- 一个国家的敌人的敌人也是这个国家的朋友。
不久后,由于粮食短缺,大陆上发生了战争,现在要建立部落联盟:如果两个国家想在一个部落中,他们两个必须是朋友。
如果一个部落中的国家越多,部落的势力就越大。如果一个部落的势力过于壮大,可能会威胁到大陆首领的地位,因此现在,大陆的首领想知道:在当前发生的所有进谏的基础上,大陆上的国家最大能建立势力多大的部落呢?
输入格式
第一行输入两个整数,表示大陆上国家的数量和进谏的次数。
接下来行,每行输入两个整数,表示国家向国家进谏并献上国礼。题目保证任何一个国家都不会向一个相同的国家进谏超过一次,且不存在自己向自己进谏的情况。
题目保证不存在和是朋友的同时和是敌人的情况。
输出格式
输出一个整数,大陆上势力最大的部落中的国家数。
样例
5 7
1 2
2 3
3 2
2 1
4 5
5 4
4 1
3
6 6
2 3
1 5
5 2
3 2
4 6
6 4
3
提示
对于样例1:和是朋友,和是朋友,和是朋友,和是敌人 、、是一个部落,和是一个部落。
对于样例2:和是朋友,和是敌人,和是敌人,和是朋友 、、是一个部落,和是一个部落,是一个部落。