/ TYWZ / 题库 /

C、团伙

C、团伙

Description

TEIAI集团共有n名员工,编号为1~n。由于长期的权力斗争,他们形成了复杂的势力网络。对于任意两名员工,他们可能是朋友,可能是敌人,也可能没什么关系。并且这种关系满足:(1)朋友的朋友是我的朋友;(2)敌人的敌人也是我的朋友。为了抱团取暖,党同伐异,员工们形成了若干团伙,每个团伙均满足:团伙内的所有人互为朋友,团伙外的每个人都不是朋友。
集团的高层认为,这种斗争关系可以加速优胜劣汰的过程,从而促进集团的盈利。他们通过暗访得到了这样的m条信息:每条信息包含3个值p,x,y,p=F表示员工x与y是朋友,p=E表示员工x与y是敌人。请你根据这m条信息,判断这些员工最多可能形成多少个团伙?

Format

Input

第1行为n和m,1<n<1000,1<=m<=5 000;
  以下m行,每行为p x y。

Output

  一个整数,表示这n个人最多可能有几个团伙。

Sample 1

Input

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

Output

  3

Limitation

2s, 65536KiB for each test case.

Hint

【样例说明】{1},{2,4,6},{3,5}

Source

高一年级信息学奥赛模拟考(二)

信息

ID
1006
难度
6
分类
(无)
标签
(无)
递交数
47
已通过
14
通过率
30%
上传者