1925 - 团队数量

题目描述

芝加哥组织了一场激烈的军事竞赛,很多国家的军人慕名而来,他们要么是队友,要么是敌人。

现建立如下规则:

  1. 我的队友的队友,是我的队友;

  2. 我的敌人的敌人也是我的队友;

两个人只要是队友,就认为他们属于同一团队,现给你若干参赛军人之间的关系,请问:最多有多少个团队?

输入

第一行是一个整数 N (2 \le N \le 1000),表示参赛的人数(从 1 编号到 N )。

第二行 M (1 \le M \le 5000),表示关于参赛者的关系信息的条数。

以下 M 行,每行可能是 F p q 或是 E p q1 \le p,q \le N),F 表示 pq 是队友,E 表示 pq 是敌人。

输入数据保证不会产生信息的矛盾。

输出

输出文件只有一行,表示最大可能的团队数。

样例

输入

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

输出

3
说明

样例解释:

[3,5] 是一个团队,[4,6] 是一个团队,由于 1412 都是敌人,24 自然成为队友,因此 [2,4,6] 成为团队,1 单独为 1 个团队,最终有 3 个团队。

来源

并查集

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 2268
通过人数 1448
金币数量 2 枚
难度 基础


上一题 下一题