虎哥迷上了"骗子与老实人"的游戏，游戏中每个人要么是老实人要么是骗子。
在每次游戏中，有n个人参与，编号分别为1到n。
游戏中共有m条“i j c”信息(1<=i,j<=n; c为imposter 或 crewmate)，每条信息为“玩家i说玩家j是骗子（imposter）或老实人(crewmate)”。
在游戏中，骗子总是说假话，而老实人总是说真话。
现在请你帮助虎哥在游戏中找到尽可能多的骗子，或确定给定的信息自相矛盾。

第一行为T（1<=T<=10000）,表示有T组测试数据。
每组测试数据的第一行为两个整数n和m(1<=n<=200000;0<=m<=50000),分别表示玩家的数量与信息的数量。接下来的m行，每行为"i j c"（1<=i,j<=n; i<>j;c为字符串 imposter 或 crewmate），允许出现相同的(i,j)。测试数据确保所有的n之和不超过200000，所有的m之和不超过500000。

每组测试数据占一行，每行包含一个整数，表示最大可能的骗子数量；若自相矛盾，则输出-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

2
4
-1
2
5

第1组测试数据中，骗子可能为2和3

第2组测试数据中，骗子可能为1,2,3,5

第3组测试数据中,出现了自相矛盾。因为（1）1说2是骗子，（2）2说1是老实人。若1是老实人，根据(1)则2是骗子；再根据（2）推出1是骗子，出现了自相矛盾。