题意：

\(n\)个人，每个人要么是敌人，要么是朋友。已知敌人一定说假话，朋友一定说真话，给出\(m\)句形如\(i,j,c\)的话，表示第\(i\)个人说第\(j\)个人的身份是\(c\)​，问敌人的最大可能数量是多少。

\(1\le n\le 2e5\)

题解：

\(2-SAT\)​只能判是否有解，找出的不是最优解

注意到如果A说B为朋友，那么A和B的身份是相同的（A假B也假，A真B也真），否则A和B身份相反（A假B真，A真B假）

也就是说，\(n\)个点中每个点要么是黑色，要么是白色，并且已知了一些关系（某些点颜色相同/相反）,

建图并黑白染色，使得染色方案没有冲突（是二分图）

在颜色相同的点之间连边权0的边，异色点之间连边权为1的边，每次要么把点染成0，要么染成1，dfs检查染色是否按照（\(col[u] \ xor\ w(u,v)=col[v]\)​​）,若不是则不合法

点与点之间的限制关系可以通过建图连边，然后在边上dfs/bfs传递和检查

// Problem: D. The Number of Imposters
// Contest: Codeforces - Codeforces Round #747 (Div. 2)
// URL: https://codeforces.com/contest/1594/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
#define ll long long
int n, m, k, tot;
int rd() {
	int s = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar();}
	return s * f;
}
struct edge {
	int v, w, nxt;
}e[1000007];
int head[maxn], eid, col[maxn], ans, ans1, ans2;
char str[20];
void init() {
	for (int i = 1; i <= n; i++) head[i] = col[i] = -1;
	eid = 0;
}
void insert(int u, int v, int w) {
	e[eid].v = v;
	e[eid].w = w;
	e[eid].nxt = head[u];
	head[u] = eid++;
}
void dfs(int u, int c) {
	col[u] = c;
	//printf("u == %d\n", u);
	if (c == 0) ans1++;
	else ans2++;
	for (int i = head[u]; ~i; i = e[i].nxt) {
		int v = e[i].v;
		if (col[v] == -1) {
			dfs(v, c^e[i].w);
		} else {
			if ((col[v]^col[u]) != e[i].w) {
				//printf("u v w == %d %d %d\n", u, v, e[i].w);
				ans = -999999999;
			}
		}
	}
}
int main() {
	int T = rd();
	while (T--) {
		n = rd(), m = rd();
		ans = 0;
		init();
		for (int i = 1; i <= m; i++) {
			int u = rd(), v = rd();
			scanf("%s", str);
			if (str[0] == 'i') {
				insert(u, v, 1);
				insert(v, u, 1);
			} else {
				insert(u, v, 0);
				insert(v, u, 0);
			}
		}
		for (int i = 1; i <= n; i++) {
			if (col[i] == -1) {
				ans1 = ans2 = 0;
				dfs(i, 0);
				ans += max(ans1, ans2);
			}
		}
		printf("%d\n", ans < 0 ? -1 : ans);
	}
}