问题 21717 --黑社会团伙

21717: 黑社会团伙

时间限制: 1 Sec  内存限制: 128 MB
提交: 96  解决: 50
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][476kb]

题目描述

众所周知,香港的黑社会组织猖獗,警方希望能摸清他们的内部构成情况,特派小生前往调查。经过长期的卧底,小生初步获得了一些资料:整个组织有n个人,任何两个认识的人不是朋友就是敌人,而且满足:①我朋友的朋友是我的朋友;②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。现在,警方委派你协助调查,拥有关于这n个人的m条信息(即某两个人是朋友,或某两个人是敌人),请你计算出这个城市最多可能有多少个团伙。

数据范围:2N20001M5000

输入

第一行包含一个整数N,第二行包含一个整数M,接下来M行描述M条信息,内容为以下两者之一:“F x y”表示xy是朋友;“E x y”表示xy是敌人(1xyN)。

输出

包含一个整数,即可能的最大团伙数。

样例输入

6
4
E 1 4
F 3 5
F 4 6
E 1 2

样例输出

3

提示

来源

[提交][状态]