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.io.DataInputStream;
  import java.io.IOException;
  import java.io.OutputStreamWriter;
  import java.io.PrintWriter;
  import java.util.LinkedList;
   
  public class Main {
   
      private static int change;
      private static int[] visited;
   
      private static void run() throws IOException {
          int n, m;
          n = in.nextInt();
          m = in.nextInt();
   
          Node[] nodes = new Node[n];
          for (int i = 0; i < n; i++) {
              nodes[i] = new Node();
              nodes[i].id = i;
          }
   
          for (int i = 0; i < m; i++) {
              int u = in.nextInt() - 1;
              int v = in.nextInt() - 1;
              String s = in.next();
   
              Comment comment = new Comment();
              comment.source = nodes[u];
              comment.target = nodes[v];
              comment.type = s.charAt(0) == 'i' ? -1 : 1;
   
              nodes[u].comments_as_source.add(comment);
              nodes[v].comments_as_target.add(comment);
          }
   
          int ans = 0;
          visited = new int[n];
          for (int i = 0; i < n; i++) {
              if (visited[i] == 0) {
                  change = 0;
                  int count = test(nodes[i], 1);
                  if (count == -1) {
                      ans = -1;
                      break;
                  }
                  ans += Math.max(count, change - count);
              }
          }
   
          out.println(ans);
      }
   
      private static int test(Node now, int type) {
          visited[now.id] = type;
          change++;
          int count = type == -1 ? 1 : 0;
          for (Comment comment : now.comments_as_source) {
              int target_type = type * comment.type;
              if (visited[comment.target.id] != 0 && visited[comment.target.id] != target_type) {
                  return -1;
              } else if (visited[comment.target.id] == 0) {
                  int result = test(comment.target, target_type);
                  if (result == -1) {
                      return result;
                  } else {
                      count += result;
                  }
              }
          }
   
          for (Comment comment : now.comments_as_target) {
              int source_type = type == comment.type ? 1 : -1;
              if (visited[comment.source.id] != 0 && visited[comment.source.id] != source_type) {
                  return -1;
              } else if (visited[comment.source.id] == 0) {
                  int result = test(comment.source, source_type);
                  if (result == -1) {
                      return -1;
                  } else {
                      count += result;
                  }
              }
          }
          return count;
      }
   
      private static class Node {
          int id;
          LinkedList<Comment> comments_as_source = new LinkedList<>();
          LinkedList<Comment> comments_as_target = new LinkedList<>();
      }
   
      private static class Comment {
          Node source, target;
          int type;
      }
   
      public static void main(String[] args) throws IOException {
          in = new Reader();
          out = new PrintWriter(new OutputStreamWriter(System.out));
   
          int t = in.nextInt();
          for (int i = 0; i < t; i++) {
              run();
          }
   
          out.flush();
          in.close();
          out.close();
      }
   
      private static int gcd(int a, int b) {
          if (a == 0 || b == 0)
              return 0;
          while (b != 0) {
              int tmp;
              tmp = a % b;
              a = b;
              b = tmp;
          }
          return a;
      }
   
      static final long mod = 1000000007;
   
      static long pow_mod(long a, long b) {
          long result = 1;
          while (b != 0) {
              if ((b & 1) != 0) result = (result * a) % mod;
              a = (a * a) % mod;
              b >>= 1;
          }
          return result;
      }
   
      private static long multiplied_mod(long... longs) {
          long ans = 1;
          for (long now : longs) {
              ans = (ans * now) % mod;
          }
          return ans;
      }
   
      @SuppressWarnings("FieldCanBeLocal")
      private static Reader in;
      private static PrintWriter out;
   
      private static int[] read_int_array(int len) throws IOException {
          int[] a = new int[len];
          for (int i = 0; i < len; i++) {
              a[i] = in.nextInt();
          }
          return a;
      }
   
      private static long[] read_long_array(int len) throws IOException {
          long[] a = new long[len];
          for (int i = 0; i < len; i++) {
              a[i] = in.nextLong();
          }
          return a;
      }
   
      private static void print_array(int[] array) {
          for (int now : array) {
              out.print(now);
              out.print(' ');
          }
          out.println();
      }
   
      private static void print_array(long[] array) {
          for (long now : array) {
              out.print(now);
              out.print(' ');
          }
          out.println();
      }
   
      static class Reader {
          private static final int BUFFER_SIZE = 1 << 16;
          private final DataInputStream din;
          private final byte[] buffer;
          private int bufferPointer, bytesRead;
   
          Reader() {
              din = new DataInputStream(System.in);
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
   
          public String readLine() throws IOException {
              final byte[] buf = new byte[1024]; // line length
              int cnt = 0, c;
              while ((c = read()) != -1) {
                  if (c == '\n') {
                      break;
                  }
                  buf[cnt++] = (byte) c;
              }
              return new String(buf, 0, cnt);
          }
   
          public int nextSign() throws IOException {
              byte c = read();
              while ('+' != c && '-' != c) {
                  c = read();
              }
              return '+' == c ? 0 : 1;
          }
   
          private static boolean isSpaceChar(int c) {
              return !(c >= 33 && c <= 126);
          }
   
          public int skip() throws IOException {
              int b;
              // noinspection ALL
              while ((b = read()) != -1 && isSpaceChar(b)) {
                  ;
              }
              return b;
          }
   
          public char nc() throws IOException {
              return (char) skip();
          }
   
          public String next() throws IOException {
              int b = skip();
              final StringBuilder sb = new StringBuilder();
              while (!isSpaceChar(b)) { // when nextLine, (isSpaceChar(b) && b != ' ')
                  sb.appendCodePoint(b);
                  b = read();
              }
              return sb.toString();
          }
   
          public int nextInt() throws IOException {
              int ret = 0;
              byte c = read();
              while (c <= ' ') {
                  c = read();
              }
              final boolean neg = c == '-';
              if (neg) {
                  c = read();
              }
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
   
              if (neg) {
                  return -ret;
              }
              return ret;
          }
   
          public long nextLong() throws IOException {
              long ret = 0;
              byte c = read();
              while (c <= ' ') {
                  c = read();
              }
              final boolean neg = c == '-';
              if (neg) {
                  c = read();
              }
              do {
                  ret = ret * 10 + c - '0';
              }
              while ((c = read()) >= '0' && c <= '9');
              if (neg) {
                  return -ret;
              }
              return ret;
          }
   
          public double nextDouble() throws IOException {
              double ret = 0, div = 1;
              byte c = read();
              while (c <= ' ') {
                  c = read();
              }
              final boolean neg = c == '-';
              if (neg) {
                  c = read();
              }
   
              do {
                  ret = ret * 10 + c - '0';
              }
              while ((c = read()) >= '0' && c <= '9');
   
              if (c == '.') {
                  while ((c = read()) >= '0' && c <= '9') {
                      ret += (c - '0') / (div *= 10);
                  }
              }
   
              if (neg) {
                  return -ret;
              }
              return ret;
          }
   
          private void fillBuffer() throws IOException {
              bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
              if (bytesRead == -1) {
                  buffer[0] = -1;
              }
          }
   
          private byte read() throws IOException {
              if (bufferPointer == bytesRead) {
                  fillBuffer();
              }
              return buffer[bufferPointer++];
          }
   
          public void close() throws IOException {
              din.close();
          }
   
      }
  }