CF1594D.The Number of Imposters

Theofanis started playing the new online game called "Among them". However, he always plays with Cypriot players, and they all have the same name: "Andreas" (the most common name in Cyprus).

In each game, Theofanis plays with $n$ other players. Since they all have the same name, they are numbered from $1$ to $n$.

The players write $m$ comments in the chat. A comment has the structure of "$i$ $j$ $c$" where $i$ and $j$ are two distinct integers and $c$ is a string ($1 \le i, j \le n$; $i \neq j$; $c$ is either imposter or crewmate). The comment means that player $i$ said that player $j$ has the role $c$.

An imposter always lies, and a crewmate always tells the truth.

Help Theofanis find the maximum possible number of imposters among all the other Cypriot players, or determine that the comments contradict each other (see the notes for further explanation).

Note that each player has exactly one role: either imposter or crewmate.

西奥法尼斯开始玩一款名为“Among Us”的新在线游戏。然而，他总是和塞浦路斯玩家一起玩，而这些玩家的名字全都一样：“安德烈亚斯”（塞浦路斯最常见的名字）。

在每局游戏中，西奥法尼斯与 $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）总是说真话。

请帮助西奥法尼斯求出其余塞浦路斯玩家中可能的最大冒险者人数；若所有评论相互矛盾，则判定为不可能（详见注释说明）。

注意：每位玩家有且仅有一种身份，即要么是冒险者（imposter），要么是船员（crewmate）。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of each test case follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$; $0 \le m \le 5 \cdot 10^5$) — the number of players except Theofanis and the number of comments.

Each of the next $m$ lines contains a comment made by the players of the structure "$i$ $j$ $c$" where $i$ and $j$ are two distinct integers and $c$ is a string ($1 \le i, j \le n$; $i \neq j$; $c$ is either imposter or crewmate).

There can be multiple comments for the same pair of $(i, j)$.

It is guaranteed that the sum of all $n$ does not exceed $2 \cdot 10^5$ and the sum of all $m$ does not exceed $5 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。随后是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$；$0 \le m \le 5 \cdot 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 \cdot 10^5$，且所有测试用例中 $m$ 的总和不超过 $5 \cdot 10^5$。

For each test case, print one integer — the maximum possible number of imposters. If the comments contradict each other, print $-1$.

对于每个测试用例，输出一个整数——最多可能的冒名顶替者数量。如果评论相互矛盾，则输出 $-1$。

In the first test case, imposters can be Andreas $2$ and $3$.

In the second test case, imposters can be Andreas $1$, $2$, $3$ and $5$.

In the third test case, comments contradict each other. This is because player $1$ says that player $2$ is an imposter, and player $2$ says that player $1$ is a crewmate. If player $1$ is a crewmate, then he must be telling the truth, so player $2$ must be an imposter. But if player $2$ is an imposter then he must be lying, so player $1$ can't be a crewmate. Contradiction.

在第一个测试用例中，冒名顶替者可以是玩家 $2$ 和 $3$。

在第二个测试用例中，冒名顶替者可以是玩家 $1$、$2$、$3$ 和 $5$。

在第三个测试用例中，发言内容相互矛盾。这是因为玩家 $1$ 称玩家 $2$ 是冒名顶替者，而玩家 $2$ 称玩家 $1$ 是船员。若玩家 $1$ 是船员，则他必定说真话，因此玩家 $2$ 必定是冒名顶替者；但若玩家 $2$ 是冒名顶替者，则他必定在说谎，因此玩家 $1$ 不可能是船员。矛盾。