#835. [BalticOI 2003] 团伙 (Day 2)

[BalticOI 2003] 团伙 (Day 2)

题目描述

现在有 nn 个人,他们之间有可能两种关系:朋友和敌人。当然,他们可能没见过面,所以没有直接关系。我们只知道:

  • 一个人的朋友的朋友是朋友
  • 一个人的敌人的敌人是朋友

现在要对这些人进行组团。如果两个人是朋友,那么这两个人一定在同一个团体中,并且一个人只能加入一个团体。请求出这些人中最多可能有的团体数。

输入格式

第一行输入一个整数 nn 代表人数。

第二行输入一个整数 mm 表示接下来要列出 mm 个关系。

接下来 mm 行,每行一个字符 optopt 和两个整数 p,qp,q,分别代表关系(朋友或敌人),有关系的两个人之中的第一个人和第二个人。其中 optopt 有两种可能:

  • 如果 optopt 为 F,则表明 pp 和 qq 是朋友。
  • 如果 optopt 为 E,则表明 pp 和 qq 是敌人。

输出格式

一行一个整数代表最多的团体数。

样例

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

题目来源:洛谷 P1892