P1892 [BalticOI 2003] 团伙 (Day 2)

题目描述

现在有 $n$ 个人,他们之间有可能两种关系:朋友和敌人。当然,他们可能没见过面,所以没有直接关系。我们**只**知道: - 一个人的朋友的朋友是朋友 - 一个人的敌人的敌人是朋友 现在要对这些人进行组团。如果两个人是朋友,那么这两个人一定在同一个团体中,并且一个人只能加入一个团体。请求出这些人中最多可能有的团体数。

输入格式

第一行输入一个整数 $n$ 代表人数。 第二行输入一个整数 $m$ 表示接下来要列出 $m$ 个关系。 接下来 $m$ 行,每行一个字符 $opt$ 和两个整数 $p,q$,分别代表关系(朋友或敌人),有关系的两个人之中的第一个人和第二个人。其中 $opt$ 有两种可能: - 如果 $opt$ 为 `F`,则表明 $p$ 和 $q$ 是朋友。 - 如果 $opt$ 为 `E`,则表明 $p$ 和 $q$ 是敌人。

输出格式

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

说明/提示

对于本题的测试数据,并非每两个人之间都有关系,或者说,我们可能不知道某两个人之间的关系。 对于 $100\%$ 的数据,$2 \le n \le 1000$,$1 \le m \le 5000$,$1 \le p,q \le n$。