CF1594D The Number of Imposters

Theofanis 开始玩一款名为 “Among them” 的新网络游戏。然而，他总是和塞浦路斯玩家一起玩，而他们都叫 “Andreas”（这是塞浦路斯最常见的名字）。 在每一局游戏中，Theofanis 会和另外 $n$ 名玩家一起玩。由于他们的名字都相同，所以用 $1$ 到 $n$ 编号。 玩家们在聊天中会写下 $m$ 条评论。每条评论的格式为 “$i$ $j$ $c$”，其中 $i$ 和 $j$ 是两个不同的整数，$c$ 是一个字符串（$1 \le i, j \le n$，$i \neq j$，$c$ 只能是 imposter 或 crewmate）。这条评论的意思是第 $i$ 号玩家说第 $j$ 号玩家的身份是 $c$。 冒充者（imposter）总是说谎，船员（crewmate）总是说真话。 请帮助 Theofanis 求出在所有塞浦路斯玩家中，冒充者的最大可能人数，或者判断这些评论是否互相矛盾（见提示部分的进一步说明）。 注意，每个玩家的身份只能是冒充者或船员中的一种。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例的描述如下。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \times 10^5$，$0 \le m \le 5 \times 10^5$），分别表示除 Theofanis 外的玩家人数和评论条数。 接下来的 $m$ 行，每行包含一条评论，格式为 “$i$ $j$ $c$”，其中 $i$ 和 $j$ 是两个不同的整数，$c$ 是一个字符串（$1 \le i, j \le n$，$i \neq j$，$c$ 只能是 imposter 或 crewmate）。 同一对 $(i, j)$ 可能会有多条评论。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$，$m$ 的总和不超过 $5 \times 10^5$。

对于每个测试用例，输出一个整数，表示冒充者的最大可能人数。如果评论之间存在矛盾，则输出 $-1$。

在第一个测试用例中，冒充者可以是 Andreas 2 和 3。 在第二个测试用例中，冒充者可以是 Andreas 1、2、3 和 5。 在第三个测试用例中，评论之间存在矛盾。因为玩家 1 说玩家 2 是冒充者，而玩家 2 说玩家 1 是船员。如果玩家 1 是船员，那么他一定说真话，所以玩家 2 必须是冒充者。但如果玩家 2 是冒充者，他一定说谎，所以玩家 1 不可能是船员。矛盾。 由 ChatGPT 4.1 翻译