Background

“核战·桃仁杀”（game）

【题目描述】

n位同学（编号从1到n）在玩一个叫作“核战·桃仁杀”的游戏，游戏规则是这样的：初始时，每人会摸取一张确认自己身份的卡片，身份只有两种类型——“好人” 或者 “坏人”（初始时只有他们自己知道自己的真实身份）。

接下来玩m轮游戏，每一轮都会由系统产生一对数字i和j（1≤i,j≤n, i ≠ j），编号为i的同学可以查看到编号为j的同学的真实身份，并汇报同学j的身份。汇报规则如下：

若 i是好人，j是好人，则i会汇报j是好人；

若 i是好人，j是坏人，则i会汇报j是坏人；

若 i是坏人，j是好人，则i会汇报j是坏人；

若 i是坏人，j是坏人，则i会汇报j是好人。

当他们在玩这个游戏的时候，一旁的禾木记录下了上述m轮信息。禾木想知道，根据这 m 轮信息，可以推测这 n位同学中“坏人”最多有多少人？请你帮助他解决这个问题。

【输入格式】

第一行，输入两个整数n和m，以一个空格分隔，分别表示玩游戏的人数和游戏轮数（1≤n ≤2×10​^5^​, 0≤m≤5×10​^5^​）。

接下来m 行，每行包含一轮信息 “i j c”，其中i和j是两个各不相同的整数，c是一个字符串，表示编号为i的同学汇报了编号为j的同学的信息（1≤i,j≤n, i≠j，c为good或bad，当c为good时，表示i汇报j是好人；当c为bad时，表示i汇报j是坏人）。

【输出格式】

如果这 m 轮汇报信息无法得到一种合法的情况（有可能是因为有的同学没有按照游戏规则汇报信息），那么输出整数−1。否则，输出一个整数，表示满足 m 轮要求的情况下，“坏人”的最多人数。

【样例1输入】

5 4
1 3 good
2 5 good
2 4 bad
3 4 bad

【样例1输出】

4

【样例1解释】

坏人人数最多的一种情况是：1、2、3和5是坏人，4是好人。

【样例2输入】

2 2
1 2 bad
2 1 good

【样例2输出】

-1

【样例2解释】

若 1汇报了2是坏人，则以下两种情况中必然有一个是成立的：

① 1是好人，2是坏人；

② 1是坏人，2是好人。

这两种情况下，2 都不可能会汇报1是好人，因此这是一种不合法的情况。

【样例3】

见选手目录下的game/game3.in与game/game3.ans（见CCF官方网站）。

【数据范围与提示】

共20组测试数据，其中：

第1 至第4组测试数据，n,m≤10；

第5 至第10组测试数据，n,m≤1000；

第11组测试数据，n=10000, m=0；

第12组测试数据，n=10000, m=9999，所有轮中的i 都为1；

第13 至第20组测试数据，1≤n≤2×10​^5^​, 0≤m≤5×10​^5^​。

提示

将问题转换成图论模型。若 i汇报j是好人，则在节点i和j之间连一条权值为0的双向边；若i汇报j是坏人，则在节点i和j之间连一条权值为1的双向边。然后对图中的n个节点进行“染色”操作，染色共需两种颜色，设为“黑色”（用1表示）和“白色”（用0 表示）。

对于当前节点u，设与其邻接的一条边的权值为w，对应的另一个节点编号为v，则依次进行如下判断。

（1）若节点v没有访问过，则分为如下两种情况。

● 若 w=1，则节点v染与节点u相反的颜色。

● 若 w=0，则节点v染与节点u相同的颜色。

（2）若节点v已访问过，则分为如下两种情况。

● 若 w=1且节点u和节点v的颜色相同，说明是不合法的情况，直接退出。

● 若 w=0且节点u和节点v的颜色不同，说明是不合法的情况，直接退出。

你可以使用dfs()函数进行染色操作。

对于同一个连通块，运行一遍dfs()函数能够得到连通块内黑色的节点个数和白色的节点个数，两者的较大值就是该连通块内对应的“坏人”的最大数量。对每一个连通块中计算出来的“坏人”最大数量进行累加，就能够得到“坏人”的最大人数了。

Limitation

1s, 1024KiB for each test case.