Theofanis 开始玩名为“Among They”的新在线游戏。然而,他总是和塞浦路斯球员一起踢球,他们都有相同的名字:“安德烈亚斯”(塞浦路斯最常见的名字)。
在每场比赛中,Theofanis 都会与 $$$n$$$ 个其他玩家一起玩。由于它们都具有相同的名称,因此它们的编号从 $$$1$$$ 到 $$$n$$$。
玩家在聊天中写下 $$$m$$$ 评论。注释的结构为“$$$i$$$ $$$j$$$ $$$c$$$”,其中 $$$i$$$ 和 $$$j$$$ 是两个不同的整数,$$$c$$$ 是一个字符串($$$1 \le i, j \le n$$$; $$$i \neq j$$$; $$$c$$$ 是冒名顶替者或船员)。该评论表示玩家 $$$i$$$ 表示玩家 $$$j$$$ 具有角色 $$$c$$$。
冒名顶替者总是撒谎,而船员总是说实话。
帮助 Theofanis 找到所有其他塞浦路斯玩家中冒名顶替者的最大可能数量,或确定评论相互矛盾(请参阅注释以获取进一步解释)。
请注意,每个玩家都只有一个角色:冒名顶替者或队友。
输入
第一行包含一个整数 $$$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$$$ 要么是冒名顶替者,要么是船员)。
同一对 $$$(i, j)$$$ 可以有多个注释。
保证所有 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$ 并且所有 $$$m$$$ 的总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数——冒名顶替者的最大可能数量。如果注释相互矛盾,则打印 $$$-1$$$。
示例
输入 #1
5 3 2 1 2 imposter 2 3 crewmate 5 4 1 3 crewmate 2 5 crewmate 2 4 imposter 3 4 imposter 2 2 1 2 imposter 2 1 crewmate 3 5 1 2 imposter 1 2 imposter 3 2 crewmate 3 2 crewmate 1 3 imposter 5 0
输出 #1
2 4 -1 2 5
注意
在第一个测试用例中,冒名顶替者可以是 Andreas $$$2$$$ 和 $$$3$$$。
在第二个测试用例中,冒名顶替者可以是 Andreas $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$5$$$。
在第三个测试用例中,注释相互矛盾。这是因为玩家 $$$1$$$ 说玩家 $$$2$$$ 是冒名顶替者,而玩家 $$$2$$$ 说玩家 $$$1$$$ 是船员。如果玩家 $$$1$$$ 是队友,那么他说的一定是真话,所以玩家 $$$2$$$ 一定是冒名顶替者。但如果玩家 $$$2$$$ 是冒名顶替者,那么他一定在撒谎,所以玩家 $$$1$$$ 不可能是队友。矛盾。