#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring> 
#include <queue>
#define N 500005
using namespace std;
int n,m,t,f[N<<1],cnt[N<<1],vis[N<<1]; 
int findf(int k){
	if(f[k]==k)
		return k;
	return f[k]=findf(f[k]);
}
char s[20];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=(n<<1);++i)
			f[i]=i;
		for(int i=1;i<=m;++i){
			int a,b;
			scanf("%d%d%s",&a,&b,s);
			if(s[0]=='c'){
				f[findf(a)]=findf(b);
				f[findf(a+n)]=findf(b+n);
			}
			else{
				f[findf(a)]=findf(b+n);
				f[findf(a+n)]=findf(b);
			}
		}
        int ans=0;
		for(int i=1;i<=n;++i){
			if(findf(i)==findf(i+n)){
				printf("-1\n");
				goto IE;
			}
		}
		memset(cnt,0,sizeof(cnt));
		memset(vis,0,sizeof(vis));
		for(int i=n+1;i<=(n<<1);++i)
			++cnt[findf(i)];
		for(int i=1;i<=n;++i){
			if(vis[findf(i)]||vis[findf(i+n)])continue;
			ans+=max(cnt[findf(i)],cnt[findf(i+n)]);
//			cout<<ans<<' '<<cnt[findf(i)]<<' '<<cnt[findf(i+n)]<<'\n';
			vis[findf(i)]=vis[findf(i+n)]=1;
		}
		printf("%d\n",ans);
		IE:;}
	return 0;
}