description: 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 ≤ i, j ≤ n; i ≠ 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 ≤ t ≤ 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 ≤ n ≤ 2 ⋅ 10^5; 0 ≤ m ≤ 5 ⋅ 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 ≤ i, j ≤ n; i ≠ 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 ⋅ 10^5 and the sum of all m does not exceed 5 ⋅ 10^5.
  
  Output
  
  For each test case, print one integer — the maximum possible number of imposters. If the comments contradict each other, print -1.
  
  Example
  
  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.
solution: import java.util.ArrayDeque;
  import java.util.ArrayList;
  
  public class Main {
  
  	public static void main(String[] args) {
  		new Main();
  	}
  
  	public Main() {
  		FastScanner fs = new FastScanner();
  		java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  		solve(fs, out);
  		out.flush();
  	}
  
  	public void solve(FastScanner fs, java.io.PrintWriter out) {
  		int t = fs.nextInt();
  		test: while(t --> 0) {
  			int n = fs.nextInt(), m = fs.nextInt();
  			ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
  			for (int i = 0;i < 2 * n;++ i) graph.add(new ArrayList<>());
  			for (int i = 0;i < m;++ i) {
  				int u = fs.nextInt() - 1, v = fs.nextInt() - 1;
  				if (fs.next().equals("crewmate")) {
  					graph.get(u).add(v);
  					graph.get(v).add(u);
  					graph.get(u + n).add(v + n);
  					graph.get(v + n).add(u + n);
  				} else {
  					graph.get(u).add(v + n);
  					graph.get(v).add(u + n);
  					graph.get(u + n).add(v);
  					graph.get(v + n).add(u);
  				}
  			}
  			boolean[] use = new boolean[n];
  			boolean[] use2 = new boolean[2 * n];
  			int ans = 0;
  			for (int i = 0;i < n;++ i) {
  				if (use[i]) continue;
  				use[i] = use2[i] = true;
  				ArrayDeque<Integer> bfs = new ArrayDeque<>();
  				bfs.add(i);
  				int crew = 1, count = 1;
  				while(!bfs.isEmpty()) {
  					int tmp = bfs.poll();
  					for (int j : graph.get(tmp)) {
  						if (use[j % n]) {
  							if (use2[j]) continue;
  							out.println(-1);
  							continue test;
  						} else {
  							use[j % n] = use2[j] = true;
  							bfs.add(j);
  							if (j < n) ++ crew;
  							++ count;
  						}
  					}
  				}
  				ans += Math.max(crew, count - crew);
  			}
  			out.println(ans);
  		}
  	}
  
  	final int MOD = 1_000_000_007;
  	int plus(int n, int m) {
  		int sum = n + m;
  		if (sum >= MOD) sum -= MOD;
  		return sum;
  	}
  	int minus(int n, int m) {
  		int sum = n - m;
  		if (sum < 0) sum += MOD;
  		return sum;
  	}
  	int times(int n, int m) {
  		return (int)((long)n * m % MOD);
  	}
  	int divide(int n, int m) {
  		return times(n, IntMath.pow(m, MOD - 2, MOD));
  	}
  	int[] fact, invf;
  	void calc(int len) {
  		len += 2;
  		fact = new int[len];
  		invf = new int[len];
  		fact[0] = fact[1] = invf[0] = invf[1] = 1;
  		for (int i = 2;i < fact.length;++ i) fact[i] = times(fact[i - 1], i);
  		invf[len - 1] = divide(1, fact[len - 1]);
  		for (int i = len - 1;i > 1;-- i) invf[i - 1] = times(i, invf[i]);
  	}
  	int comb(int n, int m) {
  		if (n < m) return 0;
  		return times(fact[n], times(invf[n - m], invf[m]));
  	}
  }
  
  class FastScanner {
  
  	private final java.io.InputStream in = System.in;
  	private final byte[] buffer = new byte[8192];
  	private int ptr = 0;
  	private int buflen = 0;
  
  	private boolean hasNextByte() {
  		if (ptr < buflen) return true;
  		ptr = 0;
  		try {
  			buflen = in.read(buffer);
  		} catch (java.io.IOException e) {
  			e.printStackTrace();
  		}
  		return buflen > 0;
  	}
  
  	private byte readByte() {
  		return hasNextByte() ? buffer[ptr++ ] : -1;
  	}
  
  	private static boolean isPrintableChar(byte c) {
  		return 32 < c || c < 0;
  	}
  
  	private static boolean isNumber(int c) {
  		return '0' <= c && c <= '9';
  	}
  
  	public boolean hasNext() {
  		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
  			ptr++ ;
  		return hasNextByte();
  	}
  
  	public String next() {
  		if (!hasNext()) throw new java.util.NoSuchElementException();
  		StringBuilder sb = new StringBuilder();
  		byte b;
  		while (isPrintableChar(b = readByte()))
  			sb.appendCodePoint(b);
  		return sb.toString();
  	}
  
  	public final char nextChar() {
  		if (!hasNext()) throw new java.util.NoSuchElementException();
  		return (char)readByte();
  	}
  
  	public final long nextLong() {
  		if (!hasNext()) throw new java.util.NoSuchElementException();
  		long n = 0;
  		try {
  			byte b = readByte();
  			if (b == '-') {
  				while (isNumber(b = readByte()))
  					n = n * 10 + '0' - b;
  				return n;
  			} else if (!isNumber(b)) throw new NumberFormatException();
  			do
  				n = n * 10 + b - '0';
  			while (isNumber(b = readByte()));
  		} catch (java.util.NoSuchElementException e) {}
  		return n;
  	}
  
  	public final int nextInt() {
  		if (!hasNext()) throw new java.util.NoSuchElementException();
  		int n = 0;
  		try {
  			byte b = readByte();
  			if (b == '-') {
  				while (isNumber(b = readByte()))
  					n = n * 10 + '0' - b;
  				return n;
  			} else if (!isNumber(b)) throw new NumberFormatException();
  			do
  				n = n * 10 + b - '0';
  			while (isNumber(b = readByte()));
  		} catch (java.util.NoSuchElementException e) {}
  		return n;
  	}
  
  	public double nextDouble() {
  		return Double.parseDouble(next());
  	}
  }
  
  class Arrays {
  
  	public static void sort(final int[] array) {
  		sort(array, 0, array.length);
  	}
  
  	public static void sort(final int[] array, int fromIndex, int toIndex) {
  		if (toIndex - fromIndex  <= 512) {
  			java.util.Arrays.sort(array, fromIndex, toIndex);
  			return;
  		}
  		sort(array, fromIndex, toIndex, 0, new int[array.length]);
  	}
  
  	private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) {
  		if (to - from  <= 512) {
  			java.util.Arrays.sort(a, from, to);
  			return;
  		}
  		final int BUCKET_SIZE = 256;
  		final int INT_RECURSION = 4;
  		final int MASK = 0xff;
  		final int shift = l << 3;
  		final int[] cnt = new int[BUCKET_SIZE + 1];
  		final int[] put = new int[BUCKET_SIZE];
  		for (int i = from; i < to; i++) ++ cnt[(a[i] >>> shift & MASK) + 1];
  		for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];
  		for (int i = from; i < to; i++) {
  			int bi = a[i] >>> shift & MASK;
  			bucket[cnt[bi] + put[bi]++] = a[i];
  		}
  		for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
  			int begin = cnt[i];
  			int len = cnt[i + 1] - begin;
  			System.arraycopy(bucket, begin, a, idx, len);
  			idx += len;
  	    }
  		final int nxtL = l + 1;
  		if (nxtL < INT_RECURSION) {
  			sort(a, from, to, nxtL, bucket);
  			if (l == 0) {
  				int lft, rgt;
  				lft = from - 1; rgt = to;
  				while (rgt - lft > 1) {
  					int mid = lft + rgt >> 1;
  					if (a[mid] < 0) lft = mid;
  					else rgt = mid;
  				}
  				reverse(a, from, rgt);
  				reverse(a, rgt, to);
  	        }
  	    }
  	}
  
  	public static void sort(final long[] array) {
  		sort(array, 0, array.length);
  	}
  
  	public static void sort(final long[] array, int fromIndex, int toIndex) {
  		if (toIndex - fromIndex  <= 512) {
  			java.util.Arrays.sort(array, fromIndex, toIndex);
  			return;
  		}
  		sort(array, fromIndex, toIndex, 0, new long[array.length]);
  	}
  
  	private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) {
  		final int BUCKET_SIZE = 256;
  		final int LONG_RECURSION = 8;
  		final int MASK = 0xff;
  		final int shift = l << 3;
  		final int[] cnt = new int[BUCKET_SIZE + 1];
  		final int[] put = new int[BUCKET_SIZE];
  		for (int i = from; i < to; i++) ++ cnt[(int) ((a[i] >>> shift & MASK) + 1)];
  		for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];
  		for (int i = from; i < to; i++) {
  			int bi = (int) (a[i] >>> shift & MASK);
  			bucket[cnt[bi] + put[bi]++] = a[i];
  		}
  		for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
  			int begin = cnt[i];
  			int len = cnt[i + 1] - begin;
  			System.arraycopy(bucket, begin, a, idx, len);
  			idx += len;
  	    }
  		final int nxtL = l + 1;
  		if (nxtL < LONG_RECURSION) {
  			sort(a, from, to, nxtL, bucket);
  			if (l == 0) {
  				int lft, rgt;
  				lft = from - 1; rgt = to;
  				while (rgt - lft > 1) {
  					int mid = lft + rgt >> 1;
  					if (a[mid] < 0) lft = mid;
  					else rgt = mid;
  				}
  				reverse(a, from, rgt);
  				reverse(a, rgt, to);
  	        }
  	    }
  	}
  
  	public static void reverse(int[] array) {
  		reverse(array, 0, array.length);
  	}
  
  	public static void reverse(int[] array, int fromIndex, int toIndex) {
  		for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) {
  			int swap = array[fromIndex];
  			array[fromIndex] = array[toIndex];
  			array[toIndex] = swap;
  		}
  	}
  
  	public static void reverse(long[] array) {
  		reverse(array, 0, array.length);
  	}
  
  	public static void reverse(long[] array, int fromIndex, int toIndex) {
  		for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) {
  			long swap = array[fromIndex];
  			array[fromIndex] = array[toIndex];
  			array[toIndex] = swap;
  		}
  	}
  
  	public static void shuffle(int[] array) {
  		java.util.Random rnd = new java.util.Random();
  		for (int i = 0;i < array.length;++ i) {
  			int j = rnd.nextInt(array.length - i) + i;
  			int swap = array[i];
  			array[i] = array[j];
  			array[j] = swap;
  		}
  	}
  
  	public static void shuffle(long[] array) {
  		java.util.Random rnd = new java.util.Random();
  		for (int i = 0;i < array.length;++ i) {
  			int j = rnd.nextInt(array.length - i) + i;
  			long swap = array[i];
  			array[i] = array[j];
  			array[j] = swap;
  		}
  	}
  }
  
  class IntMath {
  
  	public static int gcd(int a, int b) {
  		while (a != 0)
  			if ((b %= a) != 0) a %= b;
  			else return a;
  		return b;
  	}
  
  	public static int gcd(int... array) {
  		int ret = array[0];
  		for (int i = 1; i < array.length; ++i)
  			ret = gcd(ret, array[i]);
  		return ret;
  	}
  
  	public static long gcd(long a, long b) {
  		while (a != 0)
  			if ((b %= a) != 0) a %= b;
  			else return a;
  		return b;
  	}
  
  	public static long gcd(long... array) {
  		long ret = array[0];
  		for (int i = 1; i < array.length; ++i)
  			ret = gcd(ret, array[i]);
  		return ret;
  	}
  
  	public static long lcm(long a, long b) {
  		return a / gcd(a, b) * b;
  	}
  
  	public static int pow(int a, int b) {
  		int ans = 1;
  		for (int mul = a; b > 0; b >>= 1, mul *= mul)
  			if ((b & 1) != 0) ans *= mul;
  		return ans;
  	}
  
  	public static long pow(long a, long b) {
  		long ans = 1;
  		for (long mul = a; b > 0; b >>= 1, mul *= mul)
  			if ((b & 1) != 0) ans *= mul;
  		return ans;
  	}
  
  	public static int pow(int a, long b, int mod) {
  		if (b < 0) b = b % (mod - 1) + mod - 1;
  		long ans = 1;
  		for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod)
  			if ((b & 1) != 0) ans = ans * mul % mod;
  		return (int)ans;
  	}
  
  	public static int pow(long a, long b, int mod) {
  		return pow((int)(a % mod), b, mod);
  	}
  
  	public static int floorsqrt(long n) {
  		return (int)Math.sqrt(n + 0.1);
  	}
  
  	public static int ceilsqrt(long n) {
  		return n <= 1 ? (int)n : (int)Math.sqrt(n - 0.1) + 1;
  	}
  }
  