Theofanis started playing the new online game called "Among them". However, he always plays with Cypriot players, and they all have the same name: "Andreas" (the most common name in Cyprus).

In each game, Theofanis plays with $n$ other players. Since they all have the same name, they are numbered from $1$ to $n$.

The players write $m$ comments in the chat. A comment has the structure of "$i$ $j$ $c$" where $i$ and $j$ are two distinct integers and $c$ is a string ($1 \le i, j \le n$; $i \neq j$; $c$ is either imposter or crewmate). The comment means that player $i$ said that player $j$ has the role $c$.

An imposter always lies, and a crewmate always tells the truth.

Help Theofanis find the maximum possible number of imposters among all the other Cypriot players, or determine that the comments contradict each other (see the notes for further explanation).

Note that each player has exactly one role: either imposter or crewmate.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of each test case follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$; $0 \le m \le 5 \cdot 10^5$) — the number of players except Theofanis and the number of comments.

Each of the next $m$ lines contains a comment made by the players of the structure "$i$ $j$ $c$" where $i$ and $j$ are two distinct integers and $c$ is a string ($1 \le i, j \le n$; $i \neq j$; $c$ is either imposter or crewmate).

There can be multiple comments for the same pair of $(i, j)$.

It is guaranteed that the sum of all $n$ does not exceed $2 \cdot 10^5$ and the sum of all $m$ does not exceed $5 \cdot 10^5$.


-----Output-----

For each test case, print one integer — the maximum possible number of imposters. If the comments contradict each other, print $-1$.


-----Examples-----

Input
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
Output
2
4
-1
2
5


-----Note-----

In the first test case, imposters can be Andreas $2$ and $3$.

In the second test case, imposters can be Andreas $1$, $2$, $3$ and $5$.

In the third test case, comments contradict each other. This is because player $1$ says that player $2$ is an imposter, and player $2$ says that player $1$ is a crewmate. If player $1$ is a crewmate, then he must be telling the truth, so player $2$ must be an imposter. But if player $2$ is an imposter then he must be lying, so player $1$ can't be a crewmate. Contradiction.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Dynamic programming

Spanning trees


Solutions:
from sys import stdin, setrecursionlimit
from collections import defaultdict
from threading import Thread, stack_size
input = stdin.readline

def work():

	def dfs(curr):
		nonlocal c1, c2, ok
		if color[curr] == 0:
			c1 += 1
		else:
			c2 += 1
		for node in graph[curr]:
			if color[node[0]] == -1:
				color[node[0]] = color[curr] ^ node[1]
				dfs(node[0])
			elif color[node[0]] != color[curr] ^ node[1]:
				ok = False
	setrecursionlimit(2 * 10 ** 5 + 10)
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		graph = defaultdict(list)
		for __ in range(m):
			(a, b, c) = input().split()
			(a, b) = (int(a), int(b))
			if c == 'imposter':
				graph[a].append((b, 1))
				graph[b].append((a, 1))
			else:
				graph[a].append((b, 0))
				graph[b].append((a, 0))
		color = [-1 for __ in range(n + 1)]
		ans = 0
		ok = True
		for i in range(1, n + 1):
			if color[i] == -1:
				c1 = c2 = 0
				color[i] = 0
				dfs(i)
				ans += max(c1, c2)
		print(ans if ok else -1)
stack_size(10 ** 8)
Thread(target=work).start()


from sys import stdin
input = stdin.readline
from collections import deque

def bfs(p):
	global notpossible
	q = deque([p])
	who[p] = 0
	(ans, total) = (0, 0)
	while len(q):
		p = q.popleft()
		ans += who[p]
		total += 1
		for x in adj[p]:
			(node, t) = x
			if who[node] != -1:
				if t == 1 and who[p] == who[node]:
					notpossible = True
				if t == 0 and who[p] != who[node]:
					notpossible = True
				continue
			if t == 1:
				who[node] = who[p] ^ 1
			else:
				who[node] = who[p]
			q.append(node)
	return max(ans, total - ans)

def answer():
	ans = 0
	for i in range(1, n + 1):
		if who[i] != -1:
			continue
		ans += bfs(i)
		if notpossible:
			return -1
	return ans
for T in range(int(input())):
	(n, m) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		s = input().split()
		(u, v, x) = (int(s[0]), int(s[1]), s[2])
		if x == 'imposter':
			adj[u].append([v, 1])
			adj[v].append([u, 1])
		else:
			adj[u].append([v, 0])
			adj[v].append([u, 0])
	notpossible = False
	who = [-1] * (n + 1)
	print(answer())


def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import sys, os, copy, string, math, time, functools, fractions
from io import BytesIO, IOBase
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def main():
	(n, m) = LI()
	graph = defaultdict(list)
	for i in range(m):
		(i, j, c) = I().split()
		(i, j) = (int(i) - 1, int(j) - 1)
		wgt = 0
		if c == 'imposter':
			wgt = 1
		graph[i].append((j, wgt))
		graph[j].append((i, wgt))
	vis = [False] * n
	team = [None] * n
	flag = True

	@bootstrap
	def dfs(src, curr=0):
		nonlocal flag, teamA, teamB
		team[src] = curr
		if curr:
			teamA += 1
		else:
			teamB += 1
		vis[src] = True
		for (vrt, wt) in graph[src]:
			if not vis[vrt]:
				if wt:
					yield dfs(vrt, 1 - curr)
				else:
					yield dfs(vrt, curr)
			else:
				if wt and team[src] == team[vrt]:
					flag = False
				if not wt and team[src] != team[vrt]:
					flag = False
		yield True
	ans = 0
	for i in range(n):
		if not vis[i]:
			(teamA, teamB) = (0, 0)
			dfs(i, 0)
			ans += max(teamA, teamB)
			if not flag:
				break
	if not flag:
		print(-1)
		return
	print(ans)
for _ in range(II()):
	main()


class DisjointSetUnion:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def solve():
	(n, m) = map(int, input().split())
	dsu = DisjointSetUnion(2 * n)
	for i in range(m):
		(x, y, z) = map(str, input().split())
		x = int(x) - 1
		y = int(y) - 1
		if z == 'imposter':
			dsu.union(x, y + n)
			dsu.union(x + n, y)
		else:
			dsu.union(x, y)
			dsu.union(x + n, y + n)
	for i in range(n):
		if dsu.find(i) == dsu.find(i + n):
			return -1
	g = [[] for i in range(2 * n)]
	for i in range(2 * n):
		g[dsu.find(i)].append(i)
	ans = 0
	for a in g:
		cur = sum((i < n for i in a))
		ans += max(cur, len(a) - cur)
	return ans // 2
import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for i in range(t):
	print(solve())


import sys
input = sys.stdin.readline
output = print

def solve(N, M, cmts):
	adj = [set() for _ in range(N)]
	for (u, v, same) in cmts:
		adj[u].add((v, same))
		adj[v].add((u, same))
	res = 0
	color = [-1] * N
	for u in range(N):
		if color[u] != -1:
			continue
		color[u] = 0
		sizes = [1, 0]
		stack = [u]
		while stack:
			u = stack.pop()
			for (v, same) in adj[u]:
				if color[v] == -1:
					color[v] = color[u] if same else 1 - color[u]
					sizes[color[v]] += 1
					stack.append(v)
					continue
				if same and color[v] != color[u]:
					return -1
				if not same and color[v] == color[u]:
					return -1
		res += max(sizes)
	return res

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = list(map(int, input().split()))
		cmts = []
		for _ in range(M):
			(i, j, c) = input().strip().split()
			cmts.append((int(i) - 1, int(j) - 1, c == 'crewmate'))
		out = solve(N, M, cmts)
		output(out)
main()


from collections import deque
import sys
input = sys.stdin.readline

def get_root(s):
	v = []
	while not s == root[s]:
		v.append(s)
		s = root[s]
	for i in v:
		root[i] = s
	return s

def unite(s, t):
	(rs, rt) = (get_root(s), get_root(t))
	if not rs ^ rt:
		return
	if rank[s] == rank[t]:
		rank[rs] += 1
	if rank[s] >= rank[t]:
		root[rt] = rs
		size[rs] += size[rt]
	else:
		root[rs] = rt
		size[rt] += size[rs]
	return

def same(s, t):
	return True if get_root(s) == get_root(t) else False

def get_size(s):
	return size[get_root(s)]

def bfs(s):
	q = deque()
	q.append(s)
	dist[s] = 0
	c = [0, 0]
	while q:
		i = q.popleft()
		di = dist[i]
		c[di % 2] += get_size(i)
		for j in G[i]:
			if dist[j] == -1:
				q.append(j)
				dist[j] = di + 1
			elif dist[j] % 2 == di % 2:
				return [-1, -1]
	return c
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	root = [i for i in range(n + 1)]
	rank = [1 for _ in range(n + 1)]
	size = [1 for _ in range(n + 1)]
	x = []
	for _ in range(m):
		(i, j, c) = input().rstrip().split()
		(i, j) = (int(i), int(j))
		if c == 'crewmate':
			unite(i, j)
		else:
			x.append((i, j))
	G = [[] for _ in range(n + 1)]
	ok = 1
	for (i, j) in x:
		(ri, rj) = (get_root(i), get_root(j))
		if ri ^ rj:
			G[ri].append(rj)
			G[rj].append(ri)
		else:
			ok = 0
	if not ok:
		ans = -1
		print(ans)
		continue
	r = set([get_root(i) for i in range(1, n + 1)])
	r = list(r)
	l = len(r)
	dist = [-1] * (n + 1)
	ans = 0
	for s in r:
		if dist[s] == -1:
			c = bfs(s)
			if c[0] == -1:
				ok = 0
			else:
				ans += max(c)
	if not ok:
		ans = -1
	print(ans)


def naiveSolve():
	return

def solve():
	return

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)
from collections import defaultdict

def main():

	def countImpostors(initialU):
		memo = defaultdict(lambda : -1)
		st = [initialU]
		memo[initialU] = 0
		cnt = 0
		while st:
			u = st.pop()
			for (v, w) in adj[u]:
				if memo[v] != -1:
					if memo[v] != memo[u] ^ w:
						return inf
				else:
					memo[v] = memo[u] ^ w
					cnt += memo[v]
					st.append(v)
		return cnt
	t = int(input())
	allans = []
	for _ in range(t):
		(n, m) = readIntArr()
		adj = [[] for _ in range(n)]
		uf = UnionFind(n)
		for __ in range(m):
			(u, v, w) = input().split()
			u = int(u) - 1
			v = int(v) - 1
			if w[0] == 105:
				w = 1
			else:
				w = 0
			adj[u].append((v, w))
			adj[v].append((u, w))
			uf.union(u, v)
		ans = 0
		groupSize = [0] * n
		for i in range(n):
			groupSize[uf.find(i)] += 1
		vi = [False] * n
		for i in range(n):
			if vi[uf.find(i)] == False:
				vi[uf.find(i)] = True
				temp = countImpostors(i)
				if temp == inf:
					ans = temp
				else:
					temp = max(temp, groupSize[uf.find(i)] - temp)
				ans += temp
		if ans == inf:
			ans = -1
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


from collections import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def crewcheck(cur, crew, crewo, imp, impo, mode):
	qu = deque([])
	qu.append([cur, mode])
	crewset = set()
	impset = set()
	if mode == 0:
		crewset.add(cur)
	else:
		impset.add(cur)
	tot = set()
	while qu:
		x = qu.popleft()
		(x, y) = (x[0], x[1])
		if y == 0:
			for i in crew[x]:
				if 1:
					if i in impset:
						return [-1]
					if i not in tot:
						qu.append([i, 0])
						tot.add(i)
						crewset.add(i)
			for i in crewo[x]:
				if i in impset:
					return [-1]
				if i not in tot:
					qu.append([i, 0])
					tot.add(i)
					crewset.add(i)
			for i in imp[x]:
				if i in crewset:
					return [-1]
				if i not in tot:
					qu.append([i, 1])
					tot.add(i)
					impset.add(i)
			for i in impo[x]:
				if i in crewset:
					return [-1]
				if i not in tot:
					qu.append([i, 1])
					tot.add(i)
					impset.add(i)
		else:
			for i in crew[x]:
				if i in crewset:
					return [-1]
				if i not in tot:
					qu.append([i, 1])
					tot.add(i)
					impset.add(i)
			for i in crewo[x]:
				if i in crewset:
					return [-1]
				if i not in tot:
					qu.append([i, 1])
					tot.add(i)
					impset.add(i)
			for i in imp[x]:
				if i in impset:
					return [-1]
				if i not in tot:
					tot.add(i)
					qu.append([i, 0])
					crewset.add(i)
			for i in impo[x]:
				if i in impset:
					return [-1]
				if i not in tot:
					qu.append([i, 0])
					tot.add(i)
					crewset.add(i)
	return [len(impset), tot]
t = inp()
while t:
	t -= 1
	(n, m) = ma()
	if m == 0:
		print(n)
		continue
	crewsaid = [[] for i in range(n + 1)]
	crewothers = [[] for i in range(n + 1)]
	impsaid = [[] for i in range(n + 1)]
	impothers = [[] for i in range(n + 1)]
	vis = [0] * (n + 1)
	for i in range(m):
		x = input().split()
		(x, y, z) = (int(x[0]), int(x[1]), x[2])
		if z == 'imposter':
			impsaid[x].append(y)
			impothers[y].append(x)
		else:
			crewsaid[x].append(y)
			crewothers[y].append(x)
	res = 0
	tf = 0
	for i in range(1, n + 1):
		if crewsaid[i] == 0 and crewothers[i] == 0 and (impsaid[i] == 0) and (impothers[i] == 0):
			res += 1
			vis[i] = 1
			continue
		if vis[i] == 0:
			first = crewcheck(i, crewsaid, crewothers, impsaid, impothers, 0)
			second = crewcheck(i, crewsaid, crewothers, impsaid, impothers, 1)
			if first[0] == second[0] and first[0] == -1:
				tf = 1
				break
			if first[0] > second[0]:
				for j in first[1]:
					vis[j] = 1
				res += first[0]
			else:
				for j in second[1]:
					vis[j] = 1
				res += second[0]
	if tf:
		res = -1
	print(res)


from collections import defaultdict
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def input_gen_list():
	return input()[:-1].split()

def input_list():
	return list(map(int, input().split()))

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def input_int_gen():
	return map(int, input().split())
from collections import defaultdict

def find(data, i):
	if data[i] != -1:
		data[i] = find(data, data[i])
		return data[i]
	return i

def union(data, i, j):
	(pi, pj) = (find(data, i), find(data, j))
	if pi != pj:
		data[pi] = pj

def connected(data, i, j):
	return find(data, i) == find(data, j)
tests = inp()
for _ in range(tests):
	(n, m) = input_int_gen()
	data = [-1 for _ in range(2 * n + 2)]
	if m == 0:
		print(n)
		continue
	for _ in range(m):
		(i, j, ci) = input_gen_list()
		i = int(i)
		j = int(j)
		c = ci == 'imposter'
		union(data, i + n, j if c else j + n)
		union(data, i, j + n if c else j)
	impossible = False
	for i in range(1, n + 1):
		if connected(data, i + n, i):
			print(-1)
			impossible = True
			break
	if not impossible:
		teams = [[0, 0] for _ in range(2 * n + 2)]
		for i in range(1, n + 1):
			teams[find(data, i + n)][0] += 1
			teams[find(data, i)][1] += 1
		sumi = sum((max(x[0], x[1]) for x in teams))
		print(sumi // 2)


def main():
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def isthere(s, ind, c):
		for i in range(ind, len(s), ind + 1):
			if s[i] != c:
				return False
		return True

	def solve(n, claims):
		one = set()
		two = set()
		graph = []
		for _ in range(n + 1):
			graph.append([])
		dummy = n + 1
		for claim in claims:
			if claim[2] == 'imposter':
				graph[claim[0]].append(claim[1])
				graph[claim[1]].append(claim[0])
			else:
				graph.append([])
				graph[dummy].append(claim[1])
				graph[claim[1]].append(dummy)
				graph[dummy].append(claim[0])
				graph[claim[0]].append(dummy)
				dummy += 1
		Max = 0
		taken = [0] * (len(graph) + 1)
		for node in range(1, n + 1):
			if taken[node]:
				continue
			one = 1
			two = 0
			queue = deque([node])
			taken[node] = 1
			while queue:
				cur = queue.popleft()
				for child in graph[cur]:
					if taken[child] == taken[cur]:
						return -1
					if taken[child]:
						continue
					taken[child] = 1 if taken[cur] == 2 else 2
					if child <= n:
						if taken[child] == 1:
							one += 1
						else:
							two += 1
					queue.appendleft(child)
			Max += max(one, two)
		return Max
	t = int(input())
	ans = []
	for _ in range(t):
		(n, m) = map(int, input().split())
		claims = []
		for i in range(m):
			claim = input().split()
			claims.append([int(claim[0]), int(claim[1]), claim[2]])
		ans.append(solve(n, claims))
	p = 1
	for answer in ans:
		print(answer)
		p += 1
import sys, threading
import bisect
import math
import itertools
from sys import stdout
import heapq
from queue import PriorityQueue
from collections import deque
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


try:
	import sys
	from functools import lru_cache, cmp_to_key
	from heapq import merge, heapify, heappop, heappush
	from collections import defaultdict as dd, deque, Counter as C
	from itertools import combinations as comb, permutations as perm
	from bisect import bisect_left as bl, bisect_right as br, bisect, insort
	from time import perf_counter
	from fractions import Fraction
	import copy
	from copy import deepcopy
	import time
	starttime = time.time()
	mod = int(pow(10, 9) + 7)
	mod2 = 998244353

	def data():
		return sys.stdin.readline().strip()

	def out(*var, end='\n'):
		sys.stdout.write(' '.join(map(str, var)) + end)

	def L():
		return list(sp())

	def sl():
		return list(ssp())

	def sp():
		return map(int, data().split())

	def ssp():
		return map(str, data().split())

	def l1d(n, val=0):
		return [val for i in range(n)]

	def l2d(n, m, val=0):
		return [l1d(n, val) for j in range(m)]

	def A2(n, m):
		return [[0] * m for i in range(n)]

	def A(n):
		return [0] * n
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
ANS = []
for loop in range(L()[0]):
	(n, m) = L()
	(N, M) = (n, m)
	lis = [[] for i in range(n)]
	for lp2 in range(m):
		(x, y, c) = sl()
		x = int(x)
		y = int(y)
		x -= 1
		y -= 1
		if c[0] == 'i':
			cc = 1
		else:
			cc = 0
		lis[x].append((y, cc))
		lis[y].append((x, cc))
	state = [None] * N
	ans = 0
	flag = True
	q = deque()
	for i in range(N):
		if state[i] == None:
			zero = 0
			one = 0
			state[i] = 0
			q.append(i)
			while q:
				v = q.popleft()
				if state[v] == 0:
					zero += 1
				else:
					one += 1
				for (nex, cc) in lis[v]:
					if state[nex] == None:
						state[nex] = state[v] ^ cc
						q.append(nex)
					elif state[nex] != state[v] ^ cc:
						flag = False
						break
			if not flag:
				break
			ans += max(zero, one)
	if flag:
		ANS.append(str(ans))
	else:
		ANS.append('-1')
print('\n'.join(ANS))


def ss(n, m, d):
	v = [-1 for _ in range(n)]
	(a, b) = (0, 0)

	def pp(node):
		nonlocal a, b
		v[node] = 0
		q = [node]
		while q:
			q1 = []
			for node in q:
				if v[node] == 0:
					a += 1
				else:
					b += 1
				for (child, color) in d[node]:
					if v[child] == -1:
						v[child] = v[node] ^ color
						q1.append(child)
					elif v[child] != v[node] ^ color:
						return False
			q = q1
		return True
	ans = 0
	for i in range(n):
		if v[i] == -1:
			if pp(i):
				ans += max(a, b)
				a = 0
				b = 0
			else:
				return -1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {i: set() for i in range(n)}
	for i in range(m):
		(a, b, c) = map(str, input().split())
		(a, b) = (int(a), int(b))
		if c[0] == 'i':
			c = 1
		else:
			c = 0
		a -= 1
		b -= 1
		d[a].add((b, c))
		d[b].add((a, c))
	print(ss(n, m, d))


from collections import deque
from sys import stdin
t = int(input())
for _ in range(t):
	(n, m) = map(int, stdin.readline().split())
	graph = [[] for _ in range(n)]
	for _comment in range(m):
		(i, j, comment) = stdin.readline().split(' ')
		(i, j) = (int(i), int(j))
		tf = int(comment == 'crewmate\n')
		graph[i - 1].append((tf, j - 1))
		graph[j - 1].append((tf, i - 1))
	visited = [-1 for _ in range(n)]
	(small, big) = (0, 0)
	broken = False
	for i in range(n):
		cnt0 = 0
		cnt1 = 1
		if len(graph[i]) == 0:
			visited[i] = 1
			big += 1
			small += 0
		elif visited[i] == -1:
			q = deque([i])
			visited[i] = 1
			while q:
				u = q.pop()
				for (tf, v) in graph[u]:
					if visited[v] == -1:
						key = int(visited[u] == tf)
						visited[v] = key
						if key == 0:
							cnt0 += 1
						else:
							cnt1 += 1
						q.append(v)
					elif visited[v] != int(visited[u] == tf):
						broken = True
						break
			if cnt0 >= cnt1:
				big += cnt0
				small += cnt1
			else:
				big += cnt1
				small += cnt0
	if broken:
		print(-1)
	else:
		print(big)


def naiveSolve():
	return

def solve():
	return
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)
from collections import defaultdict

def main():

	def countImpostors(initialU, initialIsImpostor):
		memo = defaultdict(lambda : -1)

		@bootstrap
		def dfs(u, isImpostor):
			if memo[u] != -1:
				if isImpostor != memo[u]:
					memo[u] = inf
			else:
				memo[u] = isImpostor
				for (v, w) in adj[u]:
					if memo[u] == inf:
						yield None
					yield dfs(v, memo[u] ^ w)
			yield None
		dfs(initialU, initialIsImpostor)
		cnt = 0
		for v in memo.values():
			cnt += v
		return cnt
	t = int(input())
	allans = []
	for _ in range(t):
		(n, m) = readIntArr()
		adj = [[] for _ in range(n)]
		uf = UnionFind(n)
		for __ in range(m):
			(u, v, w) = input().split()
			u = int(u) - 1
			v = int(v) - 1
			if w == 'imposter':
				w = 1
			else:
				w = 0
			adj[u].append((v, w))
			adj[v].append((u, w))
			uf.union(u, v)
		ans = 0
		groupSize = [0] * n
		for i in range(n):
			groupSize[uf.find(i)] += 1
		vi = [False] * n
		for i in range(n):
			if vi[uf.find(i)] == False:
				vi[uf.find(i)] = True
				temp = countImpostors(i, 0)
				if temp == inf:
					ans = temp
				else:
					temp = max(temp, groupSize[uf.find(i)] - temp)
				ans += temp
		if ans == inf:
			ans = -1
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
for _ in range(*maps()):
	(n, m) = maps()
	(gr, col) = ([[] for _ in range(n)], [-1] * n)
	for __ in range(m):
		(i, j, c) = input().split()
		x = 0 if c[0] == 'c' else 1
		(i, j) = (int(i) - 1, int(j) - 1)
		gr[i].append((j, x))
		gr[j].append((i, x))
	(ok, ans) = (True, 0)
	state = [-1] * n
	for i in range(n):
		if state[i] == -1:
			q = [i]
			(c1, c2) = (0, 0)
			state[i] = 0
			for v in q:
				if state[v] == 0:
					c1 += 1
				else:
					c2 += 1
				for (vv, xx) in gr[v]:
					if state[vv] == -1:
						state[vv] = state[v] ^ xx
						q.append(vv)
					elif state[vv] != state[v] ^ xx:
						ok = False
						break
			if not ok:
				break
			ans += max(c1, c2)
	print(ans if ok else -1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	e = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v, r) = input().split()
		u = int(u)
		v = int(v)
		e[u].append((v, r == 'imposter'))
		e[v].append((u, r == 'imposter'))
	color = [-1] * (n + 1)
	vis = [0] * (n + 1)
	ng = 0
	for i in range(1, n + 1):
		if vis[i]:
			continue
		s = [i]
		vis[i] = 1
		color[i] = 0
		newvis = set()
		while len(s):
			x = s.pop()
			newvis.add(x)
			for (y, r) in e[x]:
				if color[y] != -1 and color[x] ^ r != color[y]:
					ng = 1
					break
				if vis[y]:
					continue
				vis[y] = 1
				s.append(y)
				color[y] = color[x] ^ r
		cr = 0
		im = 0
		for x in newvis:
			if color[x]:
				im += 1
			else:
				cr += 1
		if im < cr:
			for x in newvis:
				color[x] ^= 1
	if ng == 0:
		print(color.count(1))
	else:
		print(-1)


class Comba:

	def __init__(self, mod):
		self.fact = array.array('i', [0] * MX)
		self.fact[0] = 1
		self.fact_inv = array.array('i', [0] * MX)
		self.mod = mod
		for i in range(1, MX):
			self.fact[i] = self.fact[i - 1] * i % self.mod
		self.fact_inv[MX - 1] = pow(self.fact[MX - 1], self.mod - 2, self.mod)
		for i in range(MX - 2, -1, -1):
			self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod

	def ncr(self, n, r):
		if r > n or n < 0 or r < 0:
			return 0
		return self.fact[n] * self.fact_inv[r] % self.mod * self.fact_inv[n - r] % self.mod

	def npr(self, n, r):
		if r > n or n < 0 or r < 0:
			return 0
		return self.fact[n] * self.fact_inv[n - r] % self.mod

def lcm(a, b):
	return a * b // gcd(a, b)

def rw_file():
	sys.stdin = open('', 'r')
	sys.stdout = open('', 'w')

def re(data=str):
	return data(sys.stdin.readline().rstrip())

def mp(data=str):
	return map(data, sys.stdin.readline().split())
import sys, array
from bisect import bisect_left, bisect_right, insort_left
from math import ceil, floor, log, sqrt, gcd
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
(mod, mod9, nl, MX) = (1000000007, 998244353, '\n', 200003)

def solve(tc):
	(n, m) = mp(int)
	G = [[] for i in range(n)]
	for i in range(m):
		(u, v, c) = mp()
		u = int(u) - 1
		v = int(v) - 1
		if c == 'imposter':
			G[u].append((v, 1))
			G[v].append((u, 1))
		else:
			G[u].append((v, 0))
			G[v].append((u, 0))
	ans = 0
	sus = [-1] * n
	S = []

	def dfs(cur):
		S.append(cur)
		sus[cur] = 1
		(imp, visited) = (1, 1)
		while S:
			u = S.pop()
			for (v, d) in G[u]:
				if sus[v] == -1:
					sus[v] = sus[u] ^ d
					visited += 1
					if sus[v]:
						imp += 1
					S.append(v)
				elif sus[v] != sus[u] ^ d:
					return -1
		return max(visited - imp, imp)
	for i in range(n):
		if sus[i] == -1:
			res = dfs(i)
			if res == -1:
				print(-1)
				return
			ans += res
	print(ans)
	return None

def main():
	tests = 1
	tests = re(int)
	for case in range(1, tests + 1):
		solve(case)
main()


import sys, os, io
input = sys.stdin.readline
from collections import defaultdict

class DisjointSetUnion:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets
t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	dsu = DisjointSetUnion(n)
	imp = []
	a = []
	for i in range(m):
		(u, v, c) = input().split()
		(u, v) = (int(u) - 1, int(v) - 1)
		c.strip()
		if c == 'crewmate':
			dsu.union(u, v)
		else:
			imp.append([u, v])
	for i in range(len(imp)):
		imp[i][0] = dsu.find(imp[i][0])
		imp[i][1] = dsu.find(imp[i][1])
	g = [[] for i in range(n)]
	for i in range(len(imp)):
		g[imp[i][0]].append(imp[i][1])
		g[imp[i][1]].append(imp[i][0])
	flag = 0
	vis = [0] * n
	ans = 0
	for i in range(n):
		if flag:
			break
		if not vis[dsu.find(i)]:
			curr = dsu.find(i)
			stack = [curr]
			vis[curr] = 1
			cnt = 1
			group = defaultdict(lambda : -1)
			group[curr] = 0
			while stack:
				curr = stack.pop()
				now = []
				for j in g[curr]:
					if group[j] == group[curr]:
						flag = 1
					if vis[j] == 0:
						vis[j] = 1
						stack.append(j)
						group[j] = 1 - group[curr]
						now.append(j)
				for j in range(1, len(now)):
					if group[now[j]] != group[now[0]]:
						flag = 1
				if flag:
					break
			zero = []
			one = []
			for i in group:
				if group[i]:
					one.append(i)
				else:
					zero.append(i)
			oc = 0
			zc = 0
			for i in zero:
				zc += dsu.set_size(i)
			for i in one:
				oc += dsu.set_size(i)
			ans += max(oc, zc)
	if flag:
		print(-1)
	else:
		print(ans)


def naiveSolve():
	return

def solve():
	return

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, m) = readIntArr()
		adj = [[] for __ in range(n)]
		for __ in range(m):
			(u, v, w) = input().split()
			u = int(u) - 1
			v = int(v) - 1
			if w[0] == 105:
				w = 1
			else:
				w = 0
			adj[u].append((v, w))
			adj[v].append((u, w))
		val = [-1] * n
		ans = 0
		for i in range(n):
			if val[i] != -1:
				continue
			val[i] = 0
			cnt1 = 0
			cnt2 = 1
			st = [i]
			while st:
				u = st.pop()
				for (v, w) in adj[u]:
					if val[v] != -1:
						if val[v] != val[u] ^ w:
							ans = inf
					else:
						val[v] = val[u] ^ w
						st.append(v)
						if val[v] == 1:
							cnt1 += 1
						cnt2 += 1
				if ans == inf:
					break
			ans += max(cnt1, cnt2 - cnt1)
			if ans == inf:
				break
		if ans == inf:
			ans = -1
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	same = {i: set() for i in range(n)}
	diff = {i: set() for i in range(n)}
	for i in range(m):
		(i, j, c) = input().split()
		(i, j) = (int(i) - 1, int(j) - 1)
		if c == 'crewmate':
			same[i].add(j)
			same[j].add(i)
		else:
			diff[i].add(j)
			diff[j].add(i)
	inds = [-1] * n
	bad = False
	total = 0
	for i in range(n):
		if bad:
			break
		if inds[i] == -1:
			colors = {i: 1}
			layer = [i]
			while layer != []:
				newlayer = []
				for guy in layer:
					for neighbor in same[guy]:
						if neighbor not in colors:
							colors[neighbor] = colors[guy]
							newlayer.append(neighbor)
							inds[neighbor] = 1
						elif colors[neighbor] == -colors[guy]:
							bad = True
					for neighbor in diff[guy]:
						if neighbor not in colors:
							colors[neighbor] = -colors[guy]
							newlayer.append(neighbor)
							inds[neighbor] = 1
						elif colors[neighbor] == colors[guy]:
							bad = True
				layer = newlayer
			pos = 0
			neg = 0
			for guy in colors:
				if colors[guy] == 1:
					pos += 1
				else:
					neg += 1
			total += max(pos, neg)
	if bad:
		print(-1)
	else:
		print(total)


import sys
input = sys.stdin.buffer.readline

def find_root(g, x):
	answer = 1
	L = [[1, x]]
	while x != g[x][1]:
		(I, x) = g[x]
		L.append([I, x])
	while len(L) > 0:
		(I, y) = L.pop()
		g[y] = [answer, x]
		answer *= I
	return (answer, x)

def process(A, n):
	g = {}
	root_dict = {}
	A2 = {}
	for (a, b, c) in A:
		if (a, b) not in A2:
			A2[a, b] = c
		elif A2[a, b] != c:
			return -1
	for (a, b) in A2:
		c = A2[a, b]
		if c[0] == 'i':
			if a not in g and b not in g:
				g[a] = [-1, b]
				g[b] = [1, b]
			elif a not in g:
				(I, r) = find_root(g, b)
				g[a] = [-1, b]
			elif b not in g:
				(I, r) = find_root(g, a)
				g[b] = [-1, a]
			else:
				(I1, r1) = find_root(g, a)
				(I2, r2) = find_root(g, b)
				if r1 == r2:
					if I1 == I2:
						return -1
				elif I1 == I2:
					g[r1] = [-1, r2]
				else:
					g[r1] = [1, r2]
		elif a not in g and b not in g:
			g[a] = [1, b]
			g[b] = [1, b]
		elif a not in g:
			(I, r) = find_root(g, b)
			g[a] = [1, b]
		elif b not in g:
			(I, r) = find_root(g, a)
			g[b] = [1, a]
		else:
			(I1, r1) = find_root(g, a)
			(I2, r2) = find_root(g, b)
			if r1 == r2:
				if I1 != I2:
					return -1
			elif I1 == I2:
				g[r1] = [1, r2]
			else:
				g[r1] = [-1, r2]
	answer = 0
	for i in range(1, n + 1):
		if i not in g:
			answer += 1
		else:
			(I, r) = find_root(g, i)
			if r not in root_dict:
				root_dict[r] = {-1: 0, 1: 0}
			root_dict[r][I] += 1
	for r in root_dict:
		(a, b) = (root_dict[r][1], root_dict[r][-1])
		answer += max(a, b)
	return answer
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	A = []
	for j in range(m):
		(a, b, c) = input().decode().split()
		a = int(a)
		b = int(b)
		c = c[0]
		A.append([a, b, c])
	answer = process(A, n)
	answer = str(answer) + '\n'
	sys.stdout.write(answer)


def var():
	return map(int, input().split())

def a():
	return list(map(int, input().split()))

def inp():
	return int(input())
import math
import copy
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
test = inp()
for _ in range(test):
	(n, q) = var()
	isContradiction = False
	col = [-1] * (n + 1)
	ans = 0
	adj = defaultdict(list)
	for _ in range(q):
		(u, v, t) = input().split()
		if t == 'imposter':
			t = 1
		else:
			t = 2
		u = int(u)
		v = int(v)
		adj[u].append((v, t))
		adj[v].append((u, t))
	for i in range(1, n + 1):
		if col[i] == -1:
			coltype1 = 1
			coltype2 = 0
			col[i] = 1
			qu = deque([i])
			while qu:
				node = qu.popleft()
				for neTy in adj[node]:
					neigh = neTy[0]
					type = neTy[1]
					if col[neigh] != -1:
						if type == 1 and col[node] == col[neigh]:
							isContradiction = True
							break
						if type == 2 and col[node] != col[neigh]:
							isContradiction = True
							break
					else:
						if type == 1:
							col[neigh] = 3 - col[node]
						else:
							col[neigh] = col[node]
						if col[neigh] == 1:
							coltype1 += 1
						else:
							coltype2 += 1
						qu.append(neigh)
			ans += max(coltype1, coltype2)
	if isContradiction:
		print(-1)
	else:
		print(ans)


from collections import deque
from typing import DefaultDict
import sys
read = sys.stdin.readline
for _ in range(int(read())):
	(n, m) = map(int, read().split())
	graph = DefaultDict(lambda : set([]))
	fakeStuff = -1
	for _ in range(m):
		(i, j, c) = read().split()
		if c == 'crewmate':
			graph[fakeStuff].add(int(j))
			graph[int(j)].add(fakeStuff)
			graph[fakeStuff].add(int(i))
			graph[int(i)].add(fakeStuff)
			fakeStuff -= 1
		else:
			graph[int(i)].add(int(j))
			graph[int(j)].add(int(i))

	def bipartite(node):
		queue = deque([node])
		tot = 0
		zeroes = 0
		ones = 0
		while queue:
			curr = queue.popleft()
			if curr > 0:
				tot += 1
			if curr > 0 and color[curr] == 0:
				zeroes += 1
			if curr > 0 and color[curr] == 1:
				ones += 1
			for adj in graph[curr]:
				if color[adj] == -1:
					color[adj] = abs(color[curr] - 1)
					queue.append(adj)
				elif color[adj] != color[curr]:
					pass
				else:
					return -1
		return max(zeroes, ones) + (tot - (zeroes + ones))
	color = {i: -1 for i in range(fakeStuff + 1, n + 1)}
	color.pop(0)
	flag = True
	ans = 0
	for num in range(1, n + 1):
		if color[num] == -1:
			color[num] = 0
			temp = bipartite(num)
			if temp == -1:
				flag = False
				break
			ans += temp
	if flag == False:
		print(-1)
	else:
		print(ans)


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for i in range(m):
		(u, v, c) = input().split()
		(u, v) = map(int, (u, v))
		if c == 'crewmate':
			graph[u].append((v, 0))
			graph[v].append((u, 0))
		else:
			graph[u].append((v, 1))
			graph[v].append((u, 1))
	val = [None] * (n + 1)
	ans = 0
	for i in range(1, n + 1):
		if val[i] is None:
			q = [i]
			val[i] = 0
			i = 0
			c = [1, 0]
			while i < len(q):
				u = q[i]
				i += 1
				for (v, w) in graph[u]:
					if val[v] is None:
						val[v] = val[u] ^ w
						c[val[v]] += 1
						q.append(v)
					elif val[v] != val[u] ^ w:
						return -1
			ans += max(c)
	return ans
for _ in range(int(input())):
	print(solve())


from collections import defaultdict, deque
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	G = defaultdict(list)
	for i in range(m):
		(x, y, s) = input().split()
		x = int(x)
		y = int(y)
		if s[0] == 'i':
			s = 1
		else:
			s = 0
		G[x].append([y, s])
		G[y].append([x, s])
	ans = 0
	vis = [0 for i in range(n + 1)]
	sus = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		if vis[i] == 0:
			cnt = 0
			Q = [[i, 0]]
			cnt1 = 0
			vis[i] = 1
			while len(Q) != 0:
				(a, val) = Q.pop()
				if val == 1:
					cnt = cnt + 1
				else:
					cnt1 = cnt1 + 1
				sus[a] = val
				for (b, x) in G[a]:
					if val == 1:
						x = (x + 1) % 2
					if vis[b] == 0:
						Q.append([b, x])
						vis[b] = 1
						sus[b] = x
					elif sus[b] != x:
						ans = -1
						break
			if ans == -1:
				break
			ans = ans + max(cnt, cnt1)
	print(ans)


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
stinput = lambda : stdin.readline()[:-1]
ii = lambda : int(stinput())
mi = lambda : map(int, stdin.readline().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, stdin.readline().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, stdin.readline().split())
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
t = ii()
for _ in range(t):
	(n, m) = mi()
	edge = [[] for i in range(n)]
	for i in range(m):
		(a, b, c) = mis()
		(a, b) = (int(a) - 1, int(b) - 1)
		d = 1
		if c[0] == 'i':
			d = -1
		edge[a].append((b, d))
		edge[b].append((a, d))
	ans = 0
	seen = [0] * n
	f = True
	for i in range(n):
		if seen[i] != 0:
			continue
		cnt = 0
		cnt2 = 0
		seen[i] = 1
		d = deque()
		d.append(i)
		while d:
			x = d.pop()
			if seen[x] == 1:
				cnt += 1
			else:
				cnt2 += 1
			for (i, j) in edge[x]:
				if seen[i] == 0:
					seen[i] = seen[x] * j
					d.append(i)
				elif seen[i] != seen[x] * j:
					f = False
		ans += max(cnt, cnt2)
	if f:
		print(ans)
	else:
		print(-1)


import sys
input = sys.stdin.readline
map_role = {'imposter': 1, 'crewmate': 0}
for _ in range(int(input())):
	(n, m) = input().split(' ')
	nocontra = True
	n = int(n)
	m = int(m)
	edges = [[] for i in range(n + 1)]
	for com in range(m):
		(i, j, c) = input().split(' ')
		i = int(i)
		j = int(j)
		c = map_role[c.strip()]
		edges[i].append((j, c))
		edges[j].append((i, c))
	role = [-1] * (n + 1)
	res = 0
	for player in range(1, n + 1):
		if role[player] == -1:
			role[player] = 0
			count = [1, 0]
			queue = [player]
			while len(queue) > 0:
				u = queue.pop()
				for edge in edges[u]:
					v = edge[0]
					status = edge[1]
					if role[v] == -1:
						role[v] = role[u] if status == 0 else 1 - role[u]
						count[role[v]] += 1
						queue.append(v)
					else:
						ans = role[u] if status == 0 else 1 - role[u]
						if role[v] != ans:
							nocontra = False
							break
				if not nocontra:
					break
			if not nocontra:
				break
			res += max(count)
	if not nocontra:
		print(-1)
	else:
		print(res)


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v, c) = inp().split()
		(u, v) = map(int, (u, v))
		if c == 'crewmate':
			g[u].append((v, 0))
			g[v].append((u, 0))
		else:
			g[u].append((v, 1))
			g[v].append((u, 1))
	val = [None] * (n + 1)
	r = 0
	for i in range(1, n + 1):
		if val[i] is None:
			q = [i]
			val[i] = 0
			i = 0
			c = [1, 0]
			while i < len(q):
				u = q[i]
				i += 1
				for (v, w) in g[u]:
					if val[v] is None:
						val[v] = val[u] ^ w
						c[val[v]] += 1
						q.append(v)
					elif val[v] != val[u] ^ w:
						print(-1)
						return
			r += max(c)
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


class UnionFind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [0] * n

	def Find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.Find(self.par[x])
			return self.par[x]

	def Unite(self, x, y):
		x = self.Find(x)
		y = self.Find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[y] += self.par[x]
				self.par[x] = y
			else:
				self.par[x] += self.par[y]
				self.par[y] = x
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def Same(self, x, y):
		return self.Find(x) == self.Find(y)

	def Size(self, x):
		return -self.par[self.Find(x)]
import sys
import io, os
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	C = []
	I = []
	for p in range(m):
		(i, j, c) = map(str, input().split())
		(i, j) = (int(i), int(j))
		(i, j) = (i - 1, j - 1)
		if c == 'crewmate':
			C.append((i, j))
		else:
			I.append((i, j))
	uf = UnionFind(n)
	flag = True
	for (i, j) in C:
		uf.Unite(i, j)
	for (i, j) in I:
		if uf.Same(i, j):
			flag = False
			break
	if not flag:
		print(-1)
		continue
	P = []
	for i in range(n):
		if uf.par[i] < 0:
			P.append(i)
	toid = {}
	for (i, p) in enumerate(P):
		toid[p] = i
	N = len(toid)
	G = [[] for i in range(N)]
	for (i, j) in I:
		pi = uf.Find(i)
		pj = uf.Find(j)
		G[toid[pi]].append(toid[pj])
		G[toid[pj]].append(toid[pi])
	ans = 0
	flag2 = True
	visit = [False] * N
	color = [-1] * N
	for i in range(N):
		if visit[i]:
			continue
		s = []
		V0 = set()
		V1 = set()
		s.append(i)
		visit[i] = True
		color[i] = 0
		V0.add(i)
		while s:
			v = s.pop()
			for u in G[v]:
				if color[u] != -1:
					if color[u] == color[v]:
						flag2 = False
						break
					else:
						continue
				color[u] = 1 - color[v]
				visit[u] = True
				s.append(u)
				if color[u] == 0:
					V0.add(u)
				else:
					V1.add(u)
		(c0, c1) = (0, 0)
		for i in V0:
			c0 += uf.Size(P[i])
		for i in V1:
			c1 += uf.Size(P[i])
		ans += max(c0, c1)
	if flag2:
		print(ans)
	else:
		print(-1)


import sys
from collections import defaultdict, deque
N = int(input())
for _ in range(N):
	adjList = defaultdict(list)
	(n, m) = map(int, input().split())
	for _ in range(m):
		(u, v, s) = input().split()
		(u, v) = (int(u), int(v))
		d = 1 if s == 'imposter' else 0
		adjList[u].append((v, d))
		adjList[v].append((u, d))
	role = [None] * (n + 1)
	ans = 0
	flag = False
	for i in range(1, n + 1):
		if role[i] is not None:
			continue
		q = deque([(i, 0)])
		role[i] = 0
		maxx = [0, 0]
		while q:
			(u, r) = q.popleft()
			maxx[r] += 1
			for (v, d) in adjList[u]:
				if role[v] is None:
					role[v] = (r + d) % 2
					q.append((v, role[v]))
				elif role[v] != (r + d) % 2:
					print(-1)
					flag = True
					break
			if flag:
				break
		if flag:
			break
		ans += max(maxx)
	if flag:
		continue
	print(ans + sum([1 for i in range(1, n + 1) if role[i] is None]))


import math
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

def mapIn():
	return map(int, input().split())

def listIn():
	return list(map(int, input().split()))

def intIn():
	return int(input())
intMax = float('inf')
intMin = float('-inf')
d4x = [1, -1, 0, 0]
d4y = [0, 0, 1, -1]
d8x = [1, -1, 0, 0, -1, -1, 1, 1]
d8y = [0, 0, 1, -1, -1, 1, -1, 1]

def checkBit(n, i):
	return n >> i & 1
mod = int(1000000000.0 + 7)

def solve():
	(n, m) = mapIn()
	imp = 'crewmate'
	fake = n + 1
	cn = [[] for _ in range(n + m + 1)]
	color = [-1] * (n + m + 1)
	mx = [0, 0]
	ans = 0
	f = True
	for i in range(m):
		(a, b, c) = input().split()
		(a, b) = (int(a), int(b))
		if c == imp:
			cn[a].append(fake)
			cn[fake].append(a)
			cn[fake].append(b)
			cn[b].append(fake)
			fake += 1
		else:
			cn[a].append(b)
			cn[b].append(a)

	def bfs(node, c):
		nonlocal f, n
		q = deque([[node, c]])
		while len(q):
			(tmp, c) = q.popleft()
			if color[tmp] == -1 and f:
				color[tmp] = c
				mx[c] += 1 if tmp <= n else 0
				c = 1 - c
				for mate in cn[tmp]:
					if color[mate] == -1:
						q.append([mate, c])
					elif color[mate] != c:
						f = False
						break
	for i in range(1, n + 1):
		if color[i] == -1:
			mx = [0, 0]
			bfs(i, 0)
			if f:
				ans += max(mx[0], mx[1])
		if not f:
			print(-1)
			return
	print(ans)
	del ans, f, mx, cn, color
t = int(input())
for tc in range(t):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, m) = map(int, input().split())
	A = [input().split() for i in range(m)]
	for i in range(m):
		A[i][0] = int(A[i][0])
		A[i][1] = int(A[i][1])
	E = [[] for i in range(n + 1)]
	for (a, b, x) in A:
		E[a].append((b, x))
		E[b].append((a, x))
	ANS = 0
	USE = [-1] * (n + 1)
	flag = 1
	for i in range(1, n + 1):
		if USE[i] == -1:
			Q = [i]
			USE[i] = 0
			sc0 = 0
			sc1 = 0
			while Q:
				x = Q.pop()
				if USE[x] == 0:
					sc0 += 1
				elif USE[x] == 1:
					sc1 += 1
				for (to, y) in E[x]:
					if y[0] == 'c':
						if USE[to] == -1:
							USE[to] = USE[x]
							Q.append(to)
						elif USE[to] != USE[x]:
							flag = 0
							break
					elif USE[to] == -1:
						USE[to] = 1 - USE[x]
						Q.append(to)
					elif USE[to] == USE[x]:
						flag = 0
						break
			ANS += max(sc0, sc1)
	if flag == 0:
		print(-1)
	else:
		print(ANS)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)

def DFS(q):
	teams = {1: {q[0]}, -1: set()}
	for i in q:
		team_i = 1 if i in teams[1] else -1
		for j in edges[i]:
			if j in teams[1]:
				team_j = 1
			elif j in teams[-1]:
				team_j = -1
			else:
				team_j = 0
			if team_j == 0:
				teams[team_i * a[i, j]].add(j)
				q.append(j)
				unseen.remove(j)
			elif team_j != team_i * a[i, j]:
				return -1
	return max(len(teams[1]), len(teams[-1]))
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	edges = dict()
	a = dict()
	flag = True
	for i in range(n):
		edges[i] = []
	for _ in range(m):
		(i, j, k) = input().split()
		(i, j) = (int(i) - 1, int(j) - 1)
		k = 1 if k == 'crewmate' else -1
		edges[i].append(j)
		edges[j].append(i)
		if (i, j) not in a:
			a[i, j] = k
			a[j, i] = k
		elif a[i, j] != k:
			flag = False
	if flag == False:
		print('-1')
		print('\n')
	else:
		unseen = set(range(n))
		max_n = 0
		for i in range(n):
			if i in unseen:
				cnt = DFS([i])
				if cnt == -1:
					break
				max_n += cnt
		if cnt == -1:
			print('-1')
			print('\n')
		else:
			print(str(max_n))
			print('\n')


from collections import defaultdict, deque
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	fine = False
	col = [-1] * (n + 1)
	ans = 0
	a = defaultdict(list)
	for _ in range(q):
		(u, v, t) = input().split()
		(u, v) = (int(u), int(v))
		t = 1 if t == 'imposter' else 2
		a[u].append((v, t))
		a[v].append((u, t))
	for i in range(1, n + 1):
		if col[i] == -1:
			c1 = 1
			c2 = 0
			col[i] = 1
			queue = deque([i])
			while queue:
				node = queue.popleft()
				for x in a[node]:
					n1 = x[0]
					type = x[1]
					if col[n1] != -1:
						if type == 1 and col[node] == col[n1]:
							fine = True
							break
						if type == 2 and col[node] != col[n1]:
							fine = True
							break
					else:
						if type == 1:
							col[n1] = 3 - col[node]
						else:
							col[n1] = col[node]
						if col[n1] == 1:
							c1 += 1
						else:
							c2 += 1
						queue.append(n1)
			ans += max(c1, c2)
	if fine:
		print(-1)
	else:
		print(ans)


from collections import defaultdict
import sys
input = sys.stdin.readline
from collections import deque

def call(u):
	q = deque()
	q.append((u, 0))
	while q:
		(u, x) = q.popleft()
		for i in g[u]:
			if tm[i[0]] == -1:
				tm[i[0]] = i[1] ^ x
				ct[tm[i[0]]] += 1
				q.append((i[0], tm[i[0]]))
			elif tm[i[0]] == i[1] ^ x:
				pass
			else:
				return -1
	return 1
t = int(input())
for _ in range(t):
	g = defaultdict(list)
	(n, m) = map(int, input().split())
	for _ in range(m):
		(u, v, st) = input().split()
		u = int(u)
		v = int(v)
		if st == 'imposter':
			g[u].append((v, 1))
			g[v].append((u, 1))
		else:
			g[u].append((v, 0))
			g[v].append((u, 0))
	tm = [-1] * (n + 1)
	ct = [0, 0]
	ans = 0
	tf = True
	for i in range(1, n + 1):
		if tm[i] == -1:
			ct[0] = 1
			ct[1] = 0
			tm[i] = 0
			if call(i) == 1:
				ans += max(ct)
				pass
			else:
				tf = False
				break
	if tf:
		print(ans)
	else:
		print(-1)


import traceback
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
import math
from collections import defaultdict as dfd, defaultdict, Counter, deque
from functools import lru_cache
from itertools import accumulate
from heapq import *
import bisect

def geti():
	return int(input())

def gets():
	return input()

def getil():
	return list(map(int, input().split()))

def getsl():
	return input().split()

def getinps(s):
	inps = s.split()
	m = {'i': geti, 's': gets, 'il': getil, 'sl': getsl}
	if len(inps) == 1:
		return m[s]()
	return [m[k]() for k in inps]

def get2d(nrows, ncols, n=0):
	return [[n] * ncols for r in range(nrows)]

def get_acc(a):
	return list(accumulate(a))

def get_ncr(n, r, mod=10 ** 9 + 7):
	num = den = 1
	r = min(r, n - r)
	for i in range(r):
		num = num * (n - i) % mod
		den = den * (i + 1) % mod
	return num * pow(den, mod - 2, mod) % mod

def get_nc2(n):
	return n * (n - 1) // 2

def get_npr(n, r):
	if n < r:
		return 0
	return math.factorial(n) // math.factorial(r)

def put(a):
	return ' '.join(map(str, a))
ALPHABETS = 'abcdefghijklmnopqrstuvwxyz'
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
inf = float('inf')
mod = 10 ** 9 + 7

class Solution:

	def main(self):
		(N, M) = getil()
		graph = dfd(list)
		for _ in range(M):
			(u, v, w) = getsl()
			w = 0 if w == 'crewmate' else 1
			(u, v) = (int(u), int(v))
			graph[u].append([v, w])
			graph[v].append([u, w])
		seen = dict()

		def solve(node):
			if node in seen:
				return 0
			q = deque([[node, 0]])
			seen[node] = 0
			cnts = Counter()
			while q:
				(node, col) = q.popleft()
				cnts[col] += 1
				for (nei, t) in graph[node]:
					t = col if t == 0 else 1 - col
					if nei in seen:
						if t != seen[nei]:
							return inf
						continue
					q.append([nei, t])
					seen[nei] = t
			return max(cnts.values())
		ans = sum((solve(node) for node in range(1, N + 1)))
		return ans if ans != inf else -1
try:
	Sol = Solution()
	Test = geti()
	for Case in range(Test):
		ans = Sol.main()
		if ans:
			print(ans)
except Exception as e:
	print(e)
	traceback.print_exc()


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	(n, k) = R()
	a = [[] for i in range(n + k + 5)]
	col = [-1] * (n + k + 5)
	fake = n + 1
	for i in range(k):
		(x, y, c) = S().split()
		x = int(x)
		y = int(y)
		if c == 'crewmate':
			a[x] += ((fake, 1),)
			a[fake] += ((x, 1),)
			a[y] += ((fake, 1),)
			a[fake] += ((y, 1),)
			fake += 1
		else:
			a[x] += ((y, 1),)
			a[y] += ((x, 1),)
	c = [0, 0]
	f = [False]

	def dfs(x):
		stk = [x]
		if col[x] == -1:
			col[x] = 1
			c[1] += 1
		while stk:
			p = stk.pop()
			for (el, cl) in a[p]:
				if col[el] == -1:
					col[el] = col[p] ^ cl
					if el <= n:
						c[col[el]] += 1
					stk += (el,)
				elif col[el] != col[p] ^ cl:
					f[0] = True
					break
	ans = 0
	for i in range(1, n + 1):
		dfs(i)
		if f[0]:
			break
		ans += max(c)
		c = [0, 0]
	print(-1 if f[0] else ans)


import os, sys
from io import BytesIO, IOBase
from collections import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda dtype: [dtype(x) for x in input().split()]
inp_2d = lambda dtype, n: [dtype(input()) for _ in range(n)]
inp_2ds = lambda dtype, n: [inp(dtype) for _ in range(n)]
inp_enu = lambda dtype: [(i, x) for (i, x) in enumerate(inp(dtype))]
inp_enus = lambda dtype, n: [[i] + inp(dtype) for i in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b

class graph:

	def __init__(self, n):
		(self.n, self.gdict) = (n, [[] for _ in range(n + 1)])

	def add_uniEdge(self, node1, node2, w=None):
		self.gdict[node1].append((node2, w))
		self.gdict[node2].append((node1, w))

	def bfs_util(self, v):
		(queue, self.visit[v], tem, f, mem1) = (deque([v]), 1, [v], 0, [0, 0, 0])
		while queue:
			s = queue.popleft()
			mem1[self.visit[s]] += 1
			for (i1, w) in self.gdict[s]:
				val = 1 if self.visit[s] != w else 2
				if self.visit[i1] == False:
					queue.append(i1)
					self.visit[i1] = val
					tem.append(i1)
				elif val != self.visit[i1]:
					return False
		return max(mem1)

	def bfs(self):
		(self.visit, ans) = ([False] * (n + 1), 0)
		for i in range(1, self.n + 1):
			if self.visit[i] == False:
				val = self.bfs_util(i)
				if not val:
					print(-1)
					break
				ans += val
		else:
			print(ans)
mem = {'imposter': 1, 'crewmate': 2}
for _ in range(int(input())):
	(n, m) = inp(int)
	g = graph(n)
	for i in range(m):
		(u, v, w) = inp(str)
		g.add_uniEdge(int(u), int(v), mem[w])
	g.bfs()


import io, os, sys
import math
import random
from queue import PriorityQueue as PQ
from bisect import bisect_left as BSL
from bisect import bisect_right as BSR
from collections import OrderedDict as OD
from collections import Counter
from itertools import permutations
from decimal import Decimal as BIGFLOAT
mod = 1000000007
sys.setrecursionlimit(10 ** 6)
try:
	f = os.open('actext.txt', os.O_RDONLY)
	input = io.BytesIO(os.read(f, os.fstat(f).st_size)).readline
except:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_ints():
	return map(int, input().decode().split())

def palindrome(s):
	mid = len(s) // 2
	for i in range(mid):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True

def check(i, n):
	if 0 <= i < n:
		return True
	else:
		return False

def dfs(node, vis, adj_list, colorarr, cimp, ncimp):
	vis[node] = True
	global bipartitie
	stk = [node]
	while len(stk) != 0:
		node = stk.pop()
		c = colorarr[node]
		for (child, imp) in adj_list[node]:
			if not vis[child]:
				vis[child] = True
				if imp == 1:
					colorarr[child] = 1 - c
					if 1 - c == 0:
						cimp[0] += 1
					else:
						ncimp[0] += 1
					stk.append(child)
				else:
					colorarr[child] = c
					if c == 0:
						cimp[0] += 1
					else:
						ncimp[0] += 1
					stk.append(child)
			elif imp == 1:
				if colorarr[child] == c:
					bipartitie = False
			elif colorarr[child] != c:
				bipartitie = False
t = int(input().decode())
for tt in range(t):
	(n, m) = get_ints()
	adj_list = [[] for i in range(n)]
	for i in range(m):
		(u, v, c) = input().decode().strip().split()
		(u, v) = (int(u) - 1, int(v) - 1)
		if c == 'crewmate':
			adj_list[u].append((v, 2))
			adj_list[v].append((u, 2))
		else:
			adj_list[u].append((v, 1))
			adj_list[v].append((u, 1))
	colorarr = [-1] * n
	vis = [False] * n
	bipartitie = True
	ans = 0
	for i in range(n):
		if not vis[i]:
			colorarr[i] = 0
			cimp = [1]
			ncimp = [0]
			dfs(i, vis, adj_list, colorarr, cimp, ncimp)
			ans += max(cimp[0], ncimp[0])
	if not bipartitie:
		print(-1)
	else:
		print(ans)


class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n
		self.n = n
		self.cnt = n

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return False
		if self.parent[x] > self.parent[y]:
			(x, y) = (y, x)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.cnt -= 1
		return True

	def same(self, x, y):
		return self.root(x) == self.root(y)

	def size(self, x):
		return -self.parent[self.root(x)]

	def count(self):
		return self.cnt

	def groups(self):
		res = [[] for _ in range(self.n)]
		for i in range(self.n):
			res[self.root(i)].append(i)
		return [group for group in res if group]
import sys
input = sys.stdin.readline
ans = []
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	edges = [list(input().split()) for _ in range(m)]
	uf = UnionFind(n)
	anti = []
	for (u, v, c) in edges:
		u = int(u) - 1
		v = int(v) - 1
		if c == 'crewmate':
			uf.merge(u, v)
		else:
			anti.append((u, v))
	ok = True
	for (u, v) in anti:
		if uf.same(u, v) and ok:
			ans.append(-1)
			ok = False
	if not ok:
		continue
	cnt = uf.cnt
	vals = [-1] * cnt
	idxs = [-1] * n
	for (i, gps) in enumerate(uf.groups()):
		vals[i] = len(gps)
		for v in gps:
			idxs[v] = i
	graph = [[] for i in range(cnt)]
	for (u, v) in anti:
		graph[idxs[u]].append(idxs[v])
		graph[idxs[v]].append(idxs[u])

	def is_bipartite(graph):
		n = len(graph)
		cols = [-1] * n
		ans = 0
		for v in range(n):
			if cols[v] != -1:
				continue
			cols[v] = 0
			cnt = [vals[v], 0]
			stack = [v]
			while stack:
				v = stack.pop()
				for nxt_v in graph[v]:
					if cols[nxt_v] != -1:
						if cols[nxt_v] == cols[v] ^ 1:
							continue
						else:
							return (False, cols, ans)
					cols[nxt_v] = cols[v] ^ 1
					cnt[cols[nxt_v]] += vals[nxt_v]
					stack.append(nxt_v)
			ans += max(cnt)
		return (True, cols, ans)
	(flag, _, res) = is_bipartite(graph)
	if flag:
		ans.append(res)
	else:
		ans.append(-1)
for res in ans:
	print(res)


def solve():
	(n, m) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v, c) = input().split()
		(u, v) = map(int, (u, v))
		if c == 'crewmate':
			g[u].append((v, 0))
			g[v].append((u, 0))
		else:
			g[u].append((v, 1))
			g[v].append((u, 1))
	val = [None] * (n + 1)
	r = 0
	for i in range(1, n + 1):
		if val[i] is None:
			q = [i]
			val[i] = 0
			i = 0
			c = [1, 0]
			while i < len(q):
				u = q[i]
				i += 1
				for (v, w) in g[u]:
					if val[v] is None:
						val[v] = val[u] ^ w
						c[val[v]] += 1
						q.append(v)
					elif val[v] != val[u] ^ w:
						print(-1)
						return
			r += max(c)
	print(r)
for _ in range(int(input())):
	solve()


from os import read
import sys
readline = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def Find(self, x):
		stack = []
		while self.parents[x] >= 0:
			stack.append(x)
			x = self.parents[x]
		for y in stack:
			self.parents[y] = x
		return x

	def Union(self, x, y):
		x = self.Find(x)
		y = self.Find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def Size(self, x):
		return -self.parents[self.Find(x)]

	def Same(self, x, y):
		return self.Find(x) == self.Find(y)

	def Members(self, x):
		root = self.Find(x)
		return [i for i in range(self.n) if self.Find(i) == root]

	def Roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def Group_Count(self):
		return len(self.Roots())

	def All_Group_Members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.Find(member)].append(member)
		return group_members

	def __str__(self):
		return '\n'.join((f'{r}: {m}' for (r, m) in self.All_Group_Members().items()))
T = int(readline())
for _ in range(T):
	(N, M) = map(int, readline().split())
	UF = UnionFind(2 * N)
	for _ in range(M):
		(i, j, c) = readline().split()
		i = int(i) - 1
		j = int(j) - 1
		if c == 'imposter':
			UF.Union(i, j + N)
			UF.Union(j, i + N)
		else:
			UF.Union(i, j)
			UF.Union(i + N, j + N)
	for i in range(N):
		if UF.Same(i, i + N):
			ans = -1
			break
	else:
		ans = 0
		AGM = UF.All_Group_Members()
		for lst in AGM.values():
			(cnt0, cnt1) = (0, 0)
			for i in lst:
				if i < N:
					cnt0 += 1
				else:
					cnt1 += 1
			ans += max(cnt0, cnt1)
		ans //= 2
	print(ans)


from collections import defaultdict, deque
from sys import *
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	d = defaultdict(list)
	a = {}
	ans = 0
	for i in range(k):
		x = list(stdin.readline().split())
		u = int(x[0])
		v = int(x[1])
		d[u].append(v)
		d[v].append(u)
		if str(u) + ' ' + str(v) in a and x[2] != a[str(u) + ' ' + str(v)]:
			ans = -1
			continue
		a[str(u) + ' ' + str(v)] = x[2]
		a[str(v) + ' ' + str(u)] = x[2]
	if ans == -1:
		stdout.write(str(ans) + '\n')
		continue
	vis = [-1] * (n + 1)
	for i in range(1, n + 1):
		if vis[i] == -1:
			q = deque([])
			vis[i] = 0
			q.append(i)
			crew = 1
			tot = 1
			while q:
				s = q.popleft()
				for j in d[s]:
					if vis[j] == -1:
						tot += 1
						q.append(j)
						if vis[s] == 0:
							if a[str(s) + ' ' + str(j)] == 'crewmate':
								vis[j] = 0
								crew += 1
							else:
								vis[j] = 1
						elif a[str(s) + ' ' + str(j)] == 'crewmate':
							vis[j] = 1
						else:
							vis[j] = 0
							crew += 1
					elif vis[s] == 0:
						if a[str(s) + ' ' + str(j)] == 'crewmate':
							if vis[j] == 1:
								ans = -1
						elif vis[j] == 0:
							ans = -1
					elif a[str(s) + ' ' + str(j)] == 'crewmate':
						if vis[j] == 0:
							ans = -1
					elif vis[j] == 1:
						ans = -1
					if ans == -1:
						break
				if ans == -1:
					break
			if ans == -1:
				break
			ans += max(tot - crew, crew)
	stdout.write(str(ans) + '\n')


import os
import sys
import math
import collections
import functools
import itertools
import heapq
import bisect
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcde'
MOD = 10 ** 9 + 7
EPS = 1e-06
INF = 10 ** 18

def Ceil(a, b):
	return a // b + int(a % b > 0)

def INT():
	return int(input())

def STR():
	return input()

def INTS():
	return tuple(map(int, input().split()))

def ARRINT():
	return [int(i) for i in input().split()]

def ARRSTR():
	return [i for i in input().split()]

def solve(n, m, g):
	state = [None] * n
	res = 0
	flag = True
	q = collections.deque([])
	for i in range(n):
		if state[i] == None:
			zero = 0
			one = 0
			state[i] = 0
			q += [i]
			while q:
				v = q.popleft()
				if state[v] == 0:
					zero += 1
				else:
					one += 1
				for (nex, cc) in g[v]:
					if state[nex] == None:
						state[nex] = state[v] ^ cc
						q.append(nex)
					elif state[nex] != state[v] ^ cc:
						flag = False
						break
			if not flag:
				break
			res += max(zero, one)
	if flag:
		print(res)
	else:
		print(-1)
for t in range(INT()):
	(n, m) = INTS()
	g = [[] for _ in range(n)]
	for _ in range(m):
		(i, j, k) = input().split()
		i = int(i) - 1
		j = int(j) - 1
		k = 1 if k[0] == 'i' else 0
		g[i] += [(j, k)]
		g[j] += [(i, k)]
	solve(n, m, g)


import io, os
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	(n, m) = map(int, input().split())
	group = [-1] * n
	neigh = [[] for i in range(n)]
	nonneigh = [[] for i in range(n)]
	for _ in range(m):
		(i, j, c) = input().split()
		i = int(i) - 1
		j = int(j) - 1
		if c[0] == ord('c'):
			neigh[i].append(j)
			neigh[j].append(i)
		elif c[0] == ord('i'):
			nonneigh[i].append(j)
			nonneigh[j].append(i)
	queue = deque()
	actual = [i for i in range(n + 1)]
	curr = 1
	for i in range(n):
		if group[i] >= 0:
			continue
		if len(neigh[i]) + len(nonneigh[i]) == 0:
			continue
		group[i] = curr
		queue.append([i, 0])
		while queue:
			(index, extra) = queue.popleft()
			for nextindex in neigh[index]:
				if group[nextindex] > 0:
					if group[nextindex] != curr + extra:
						print(-1)
						return
				else:
					group[nextindex] = curr + extra
					queue.append([nextindex, extra])
			for nextindex in nonneigh[index]:
				if group[nextindex] > 0:
					if group[nextindex] != curr + 1 - extra:
						print(-1)
						return
				else:
					group[nextindex] = curr + 1 - extra
					queue.append([nextindex, 1 - extra])
		curr += 2
	fre = [0] * curr
	for num in group:
		if num == -1:
			fre[0] += 1
		else:
			fre[num] += 1
	ans = fre[0]
	for base in range(1, len(fre), 2):
		ans += max(fre[base], fre[base + 1])
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
import sys

def input():
	return sys.stdin.readline().rstrip()

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getListGraph():
	return list(map(lambda x: int(x) - 1, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]
mod = 10 ** 9 + 7
MOD = 998244353
inf = float('inf')
eps = 10 ** (-10)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
T = getN()
for _ in range(T):
	(N, M) = getNM()
	E = [[] for i in range(N)]
	for _ in range(M):
		(a, b, s) = input().split()
		E[int(a) - 1].append([int(b) - 1, s != 'crewmate'])
		E[int(b) - 1].append([int(a) - 1, s != 'crewmate'])
	color = [-1] * N

	def bipata(start):
		color[start] = 0
		q = deque([start])
		cnt = [1, 0]
		while q:
			u = q.popleft()
			for (v, c) in E[u]:
				if color[v] == -1:
					color[v] = color[u] ^ c
					cnt[color[u] ^ c] += 1
					q.append(v)
				elif color[v] != color[u] ^ c:
					cnt = [-inf, -inf]
		return cnt
	ans = 0
	for i in range(N):
		if color[i] == -1:
			ans += max(bipata(i))
	if ans == -inf:
		print(-1)
	else:
		print(ans)


import sys
from sys import stdin
from collections import deque
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	(n, m) = map(int, stdin.readline().split())
	(N, M) = (n, m)
	lis = [[] for i in range(n)]
	for lp2 in range(m):
		(x, y, c) = stdin.readline()[:-1].split()
		x = int(x)
		y = int(y)
		x -= 1
		y -= 1
		if c[0] == 'i':
			cc = 1
		else:
			cc = 0
		lis[x].append((y, cc))
		lis[y].append((x, cc))
	state = [None] * N
	ans = 0
	flag = True
	q = deque()
	for i in range(N):
		if state[i] == None:
			zero = 0
			one = 0
			state[i] = 0
			q.append(i)
			while q:
				v = q.popleft()
				if state[v] == 0:
					zero += 1
				else:
					one += 1
				for (nex, cc) in lis[v]:
					if state[nex] == None:
						state[nex] = state[v] ^ cc
						q.append(nex)
					elif state[nex] != state[v] ^ cc:
						flag = False
						break
			if not flag:
				break
			ans += max(zero, one)
	if flag:
		ANS.append(str(ans))
	else:
		ANS.append('-1')
print('\n'.join(ANS))


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = {i: [] for i in range(1, n + 1)}
	for i in range(m):
		(a, b, c) = input().split()
		a = int(a)
		b = int(b)
		if c == 'imposter':
			l[a].append((b, 1))
			l[b].append((a, 1))
		else:
			l[a].append((b, 2))
			l[b].append((a, 2))
	col = [-1] * (n + 1)
	ans = 0
	f = 0
	q = deque([])
	for i in range(1, n + 1):
		a = 0
		b = 0
		if col[i] == -1:
			q.append(i)
			col[i] = 1
			while q:
				u = q[0]
				q.popleft()
				if col[u] == 1:
					a += 1
				else:
					b += 1
				for j in l[u]:
					(v, t) = j
					if col[v] != -1:
						if t == 1 and col[v] == col[u]:
							f = 1
						if t == 2 and col[v] != col[u]:
							f = 1
						continue
					if t == 1:
						col[v] = 3 - col[u]
					else:
						col[v] = col[u]
					q.append(v)
			ans += max(a, b)
	if f == 1:
		print(-1)
	else:
		print(ans)


import sys

def input():
	return sys.stdin.readline().strip('\n')

def cin_int_ls():
	return list(map(int, input().split()))

def cin_int():
	return int(input())
imposter = 'imposter'
crewmate = 'crewmate'

def sv(comments, ppp, nnn):
	vis = set()

	def bfs(i, role):
		tmp = {i: role}
		q = deque()
		vis.add(i)
		q.append(i)
		while len(q):
			n = q.popleft()
			role = tmp[n]
			for (nxt, r) in ppp[n].items():
				if nxt not in tmp:
					tmp[nxt] = not role ^ r
					vis.add(nxt)
					q.append(nxt)
				elif nxt in tmp and tmp[nxt] != (not role ^ r):
					raise RecursionError
			for (pre, r) in nnn[n].items():
				if pre not in tmp:
					tmp[pre] = role == r
					vis.add(pre)
					q.append(pre)
				elif pre in tmp and tmp[pre] != (role == r):
					raise RecursionError
		ans = 0
		for (k, v) in tmp.items():
			if v:
				ans += 1
		return ans
	good_man = 0
	for i in comments:
		if i not in vis:
			a = bfs(i, True)
			b = bfs(i, False)
			good_man += min(a, b)
	return good_man
from collections import defaultdict, deque

def main():
	for _ in range(cin_int()):
		(count, m) = cin_int_ls()
		ppp = defaultdict(dict)
		nnn = defaultdict(dict)
		comments = set()
		fail = False
		for _ in range(m):
			(i, j, c) = input().split()
			(i, j) = (int(i), int(j))
			comments.add(int(i))
			comments.add(int(j))
			if j in ppp[i] and ppp[i][j] != (c == crewmate):
				fail = True
			ppp[int(i)][int(j)] = c == crewmate
			nnn[int(j)][int(i)] = c == crewmate
		try:
			if fail:
				raise RecursionError
			good = sv(comments, ppp, nnn)
			print(count - good)
		except RecursionError:
			print(-1)
main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	p = [-1] * n
	for i in range(m):
		(u, v, c) = input().split()
		(u, v) = map(int, (u, v))
		d = 1
		if c == 'crewmate':
			d = 0
		G[u - 1].append([v - 1, d])
		G[v - 1].append([u - 1, d])
	ans = 0
	for i in range(n):
		if p[i] != -1:
			continue
		que = [i]
		p[i] = 1
		a = 0
		c = 0
		for pos in que:
			c += 1
			if p[pos] == 1:
				a += 1
			for (to, d) in G[pos]:
				if p[to] != -1:
					if p[to] != p[pos] ^ d:
						ans = -1000000000
				else:
					p[to] = p[pos] ^ d
					que.append(to)
		if ans < 0:
			ans = -1
			break
		ans += max(a, c - a)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque
t = int(input())

def cycle_bfs(graph, n, node):
	q = deque([node])
	color[node] = 0
	zero = 0
	one = 0
	while q:
		currnode = q.popleft()
		visited[currnode] = True
		if color[currnode] == 0:
			currcolor = 1
			if currnode <= n:
				zero += 1
		else:
			currcolor = 0
			if currnode <= n:
				one += 1
		if currnode in graph:
			for neighbour in graph[currnode]:
				if visited[neighbour] == False:
					visited[neighbour] = True
					color[neighbour] = currcolor
					q.append(neighbour)
				elif color[neighbour] != currcolor:
					return (False, 0)
	return (True, max(one, zero))
while t:
	t -= 1
	(n, m) = [int(x) for x in input().split()]
	ans = [None for x in range(n + 1)]
	graph = {x: set() for x in range(1, n + 1)}
	fake = n + 1
	visited = [False for x in range(n + 1)]
	for _ in range(m):
		(a, b, c) = [x for x in input().split()]
		a = int(a)
		b = int(b)
		if c == 'imposter':
			graph[a].add(b)
			graph[b].add(a)
		else:
			graph[fake] = set()
			graph[fake].add(a)
			graph[a].add(fake)
			graph[fake].add(b)
			graph[b].add(fake)
			fake += 1
			visited.append(False)
	color = [None for x in range(len(visited))]
	ans = True
	res = 0
	for node in range(1, n + 1):
		if visited[node] == False:
			(ans, v) = cycle_bfs(graph, n, node)
			res += v
			if ans == False:
				break
	if ans:
		print(res)
	else:
		print(-1)


from collections import defaultdict, deque
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = defaultdict(list)
	for i in range(m):
		(a, b, c) = map(str, input().split())
		(a, b) = (int(a), int(b))
		if c[0] == 'i':
			d[a].append((b, 1))
			d[b].append((a, 1))
		else:
			d[a].append((b, 2))
			d[b].append((a, 2))
	color = [-1] * (n + 1)
	q = deque()
	ans = 0
	iscon = False
	for i in range(1, n + 1):
		(c1, c2) = (0, 0)
		if color[i] == -1:
			q.append(i)
			color[i] = 1
			while len(q) > 0:
				u = q.popleft()
				if color[u] == 1:
					c1 += 1
				else:
					c2 += 1
				for val in d[u]:
					v = val[0]
					typ = val[1]
					if color[v] != -1:
						if typ == 1 and color[v] == color[u]:
							iscon = True
						if typ == 2 and color[v] != color[u]:
							iscon = True
						continue
					if typ == 1:
						color[v] = 3 - color[u]
					else:
						color[v] = color[u]
					q.append(v)
		ans += max(c1, c2)
	if iscon:
		print(-1)
	else:
		print(ans)


def solve(n, m, comments):
	neigh = [[] for _ in range(n + 1)]
	for (i, j, c) in comments:
		neigh[i].append((j, c))
		neigh[j].append((i, c))
	comments = []
	smallest_unseen = 1
	i_map = [-1] * (n + 2)
	opposite = {'c': 'i', 'i': 'c'}
	tot = 0
	while smallest_unseen <= n:
		i_map = i_map
		i_map[smallest_unseen] = 'i'
		i_count_imp = {'i': 1, 'c': 0}
		(res_imp, i_count, swap_index) = traverse(i_map, neigh, opposite, smallest_unseen, i_count_imp)
		if res_imp == -1:
			return -1
		if i_count['i'] < i_count['c']:
			for index in swap_index:
				i_map[index] = opposite[i_map[index]]
			i_count['i'] = i_count['c']
		tot += i_count['i']
		for i in range(n):
			smallest_unseen += 1
			if i_map[smallest_unseen] == -1:
				break
	return tot

def traverse(i_map, neigh, opposite, smallest_unseen, i_count):
	known = [smallest_unseen]
	swap_index = [smallest_unseen]
	while len(known) > 0:
		cur = known.pop()
		for (j, c) in neigh[cur]:
			if i_map[cur] == 'c':
				new_val = c
			else:
				new_val = opposite[c]
			if i_map[j] != -1 and i_map[j] != new_val:
				return (-1, i_count, [])
			else:
				if i_map[j] == new_val:
					continue
				i_map[j] = new_val
				swap_index.append(j)
				i_count[new_val] += 1
				known.append(j)
	return (1, i_count, swap_index)
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input().decode().strip())
for t in range(T):
	(n, m) = [int(x) for x in input().decode().strip().split(' ')]
	comments = []
	for _ in range(m):
		(i, j, c) = [x for x in input().decode().strip().split(' ')]
		comments.append((int(i), int(j), c[0]))
	resa = solve(n, m, comments)
	print(resa)