五行学说(Five Elements)

题目描述

五行学说的基本观点如下：

1. 金、木、水、火、土是万事万物的基本属性，每种物品有且仅有一种属性。
2. 属性之间有相生和相克的关系，每个属性所生的属性只有一种，所克的属性也只有一种：

• 相生关系是：水生木，木生火，火生土，土生金，金生水；
• 相克关系是：金克木，木克土，土克水，水克火，火克金。

3. 同属性之间不存在相生相克关系。若甲乙两个物体都是火属性的，则不能说甲克乙或甲生乙。

下图可以更快地理解相生相克的关系：

小 Z 的身边有的 $n$ 个物品，每个物品都应该具有五行中的一种属性。小Z对这些物品进行了 $m$ 次观察，每次观察都是会发现两种物质之间的相生或相克关系。但这些观察不一定可靠，如果本次观察与之前的记录没有矛盾，则将这条观察记录下来； 否则，直接忽视该条观察。

请你帮助小 Z 统计一下，有多少条观察是被忽略的。

输入格式

第一行：两个整数表示 $n$ 和 $m$。

第二行到第 $m$ 行：每行表示一条观察，首先有一个字符，然后有两个整数参数 $x$ 和 $y$：

• 相生关系以字母 s 开头，表示 $x$ 生 $y$；
• 相克关系以字母 k 开头，表示 $x$ 克 $y$。

输出格式

单个整数：表示输入中出现矛盾的记录条数。

样例输入 #1

3 4
k 1 2
s 1 2
k 2 3
k 3 1

样例输出 #1

2

数据范围

【样例解释】

第一条观察和第二条观察显然矛盾，第四条观察和第一、第三条观察的推论矛盾。

【数据范围】

对于 $30\%$ 的数据，$1\leq n,m\leq 10$。

对于 $60\%$ 的数据，$1\leq n,m\leq 10^3$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接