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: 							/*
  							ID: abdelra29
  		LANG: JAVA
  		PROG: zerosum
  							*/
  								/*
  								TO LEARN
  						
  								2-euler tour
  							
  								*/
  								/*
  								TO SOLVE 
  								*/
  								/*
  								bit manipulation shit
  								1-Computer Systems: A Programmer's Perspective
  								2-hacker's delight
  								*/
  								/*
  								TO WATCH
  								
  								*/
  								            import java.util.*;
  										    import java.math.*;
  										    import java.io.*; 
  										    import java.text.DecimalFormat;
  										    import java.util.stream.Collectors;
  
  
  										       public class A{
  								            static FastScanner scan=new FastScanner();
  											     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  			
  static int col[];
  static int dp[][];
  static LinkedList<special>edges[];
  static LinkedList<special>revedges[];
  static boolean vis[];
  static boolean can(int x,int e)
  {
  	if(col[x]!=-1&&col[x]!=e)
  	{
  		//out.println((x+1)+" "+e+" "+col[x]);
  		return false;
  	}
  	col[x]=e;
  	boolean is=true;
  	for(special v:revedges[x])
  	{
  		if(col[v.ed]==-1)
  		{
  			if(e==0)
  			{
  				if(v.s.equals("imposter"))
  				{
  					is=is&can(v.ed,1);
  					//col[v.ed]=1;
  				}
  				else 
  				{
  					is=is&can(v.ed,0);
  				}
  			}
  			else 
  			{
  				if(v.s.equals("imposter"))
  				{
  					is=is&can(v.ed,0);
  				}
  				else 
  				{
  					is=is&can(v.ed,1);
  				}
  			}
  		}
  
  	}
  	for(special v:edges[x])
  	{
  		if(col[v.ed]==-1)
  		{
  		    if(e==0)
  		    {
  		    	if(v.s.equals("imposter"))
  		    	{
  		    		is=is&can(v.ed,1);
  		    	}
  		    	else 
  		    	{
  		    		is=is&can(v.ed,0);
  		    	}
  		    }
  		    else 
  		    {
  		    	if(v.s.equals("imposter"))
  		    	{
  		    		is=is&can(v.ed,0);
  		    	}
  		    	else 
  		    	{
  		    		is=is&can(v.ed,1);
  		    	}
  		    }
  		}
  		else 
  		{
  			if(e==0)
  		    {
  		    	if(v.s.equals("imposter"))
  		    	{
  		    		if(col[v.ed]!=1)
  		    		{
  		    			return false;
  		    		}
  		    	}
  		    	else 
  		    	{
  		    		
  		    		if(col[v.ed]!=0)
  		    		{
  		    			return false;
  		    		}
  		    	}
  		    }
  		    else 
  		    {
  		    	if(v.s.equals("imposter"))
  		    	{
  		    		
  		    		if(col[v.ed]!=0)
  		    		{
  		    			return false;
  		    		}
  		    	}
  		    	else 
  		    	{
  		    		
  		    		if(col[v.ed]!=1)
  		    		{
  		    			return false;
  		    		}
  		    	}
  		    }
  		}
  	}
  	return is;
  }
  static int dfs(int x,int e)
  {
  	if(dp[x][e]!=-1)
  		return dp[x][e];
  	int ans=0;
  	vis[x]=true;
  	for(special v:revedges[x])
  	{
  		if(!vis[v.ed]){
  		if(e==0)
  			{
  				if(v.s.equals("imposter"))
  				{
  					//col[v.ed]=1;
  					ans+=(dfs(v.ed,1)+1);
  					//ans++;
  				}
  				else 
  				{
  					ans+=dfs(v.ed,0);
  					//col[v.ed]=0;
  				}
  			}
  			else 
  			{
  				if(v.s.equals("imposter"))
  				{
  					ans+=(dfs(v.ed,0));
  				//	col[v.ed]=0;
  				}
  				else 
  				{
  				ans+=(dfs(v.ed,1)+1);
  				//	col[v.ed]=1;
  				//	ans++;
  				}
  			}
  	}
  }
  	for(special v:edges[x])
  	{
  		if(e==1)
  		{
  			if(!vis[v.ed])
  			{
  				if(v.s.equals("imposter"))
  				{
  					ans+=(dfs(v.ed,0));
  				}
  				else 
  				{
  					ans+=(dfs(v.ed,1)+1);
  				}
  			}
  		}
  		else 
  		{
  			if(!vis[v.ed])
  			{
  				if(v.s.equals("imposter"))
  				{
  					ans+=(dfs(v.ed,1)+1);
  				}
  				else 
  				{
  					ans+=(dfs(v.ed,0));
  				}
  			}
  		}
  	}
  	return dp[x][e]=ans;
  }
  				public static void main(String[] args)  throws Exception 
  								      {
  								 /*
  								 very important tips 
  								 1-just fucking think backwards once in your shitty life
  								 2-consider brute forcing and finding some patterns and observations
  								 3-when you're in contest don't get out because you think there is no enough time
  								 4-don't get stuck on one approach 
  								 */
  							   
  				//scan=new FastScanner("money.in");
  			//	out = new PrintWriter("money.out");
  
  							
  										 							 /*
  										 READING 
  								
  										 3-Introduction to DP with Bit-masking codeforces
  										 4-Bit Manipulation hacker-earth
  										 5-read more about mobious and inclusion-exclusion 
  					 				     6-read more about Fermat little theorem
  										 */
  										 /*
  										   
  										 */
  
  		//String F="4 + 5";
  		//System.out.println( Integer.parseInt(F));			 			
  								     
  	int tt=1;
  //int sb=scan.nextInt();
  							tt=scan.nextInt();
  									int T=tt;
  									 outer:while(tt-->0)
  									    {
  									    	int n=scan.nextInt(),m=scan.nextInt();
  									    	edges=new LinkedList[n];
  									    	revedges=new LinkedList[n];
  									    	for(int i=0;i<n;i++)
  									    	{
  									    		edges[i]=new LinkedList();
  									    		revedges[i]=new LinkedList();
  									    	}
  									    	for(int i=0;i<m;i++)
  									    	{
  									    		int x=scan.nextInt()-1,y=scan.nextInt()-1;
  									    		String s=scan.next();
  									    		edges[x].add(new special(y,s));
  									    		revedges[y].add(new special(x,s));
  									    	}
  									    	col=new int[n];
  									    	Arrays.fill(col,-1);
  									    	for(int i=0;i<n;i++)
  									    	{
  									    		if(col[i]==-1&&!can(i,0))
  									    		{
  									    		//	out.println("F");
  									    			out.println(-1);
  									    			continue outer;
  									    		}
  									    	}
  									    	col=new int[n];
  									    	Arrays.fill(col,-1);
  									    	for(int i=0;i<n;i++)
  									    	{
  									    		if(col[i]==-1&&!can(i,1))
  									    		{
  									    			out.println(-1);
  									    			continue outer;
  									    		}
  									    	}
  									    	vis=new boolean[n];
  									    	int ans=0;
  									    	dp=new int[n][2];
  									    	for(int K[]:dp)
  									    		Arrays.fill(K,-1);
  									    	int ans1[]=new int[n];
  									    	int ans2[]=new int[n];
  									    	vis=new boolean[n];
  									    	for(int i=0;i<n;i++)
  									    	{
  									    		if(!vis[i])
  									    		{
  									    			ans1[i]=dfs(i,0);
  									    		}
  									    	}
  									    	vis=new boolean[n];
  									    	dp=new int[n][2];
  									    	for(int K[]:dp)
  									    		Arrays.fill(K,-1);
  									    	for(int i=0;i<n;i++)
  									    	{
  									    		if(!vis[i])
  									    		{
  									    			ans2[i]=(dfs(i,1)+1);
  									    		}
  									    	}
  									    
  									    	for(int i=0;i<n;i++)
  									    	{
  									    		//out.println(ans1[i]+" "+ans2[i]+" "+(i+1));
  									    		ans+=Math.max(ans2[i],ans1[i]);
  									    	}
  									    	out.println(ans);
  
  
  
     			
  
  						    	
  }
  									    	
  
  
  
  									    									    	
  	  			   	
  		 		
  		
  	        
  
  				out.close();
  							}
  							
  							
  
  							static class special {
  							int ed;
  							String s;
  							public special(int ed,String s)
  							{
  								this.ed=ed;
  								this.s=s;
  							}
  
  								 @Override
  										            public int hashCode() {
  										                return (int)42;
  										            }
  								  @Override
  										            public boolean equals(Object o){
  										            //	System.out.println("FUCK");
  										                if (o == this) return true;
  										                if (o.getClass() != getClass()) return false;
  										                special t = (special)o;
  										                return t.ed == ed && t.s.equals(s);
  										            }
  										          
  							}
  				
  										   
  										     static long binexp(long a,long n)
  										    {
  										        if(n==0)
  										            return 1;
  										        long res=binexp(a,n/2);
  										        if(n%2==1)
  										            return res*res*a;
  										        else 
  										            return res*res;
  										    }
  										     
  										    static long powMod(long base, long exp, long mod) {
  										           if (base == 0 || base == 1) return base;
  										           if (exp == 0) return 1;
  										           if (exp == 1) return (base % mod+mod)%mod;
  										           long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
  										           R *= R;
  										           R %= mod;
  										           if ((exp & 1) == 1) {
  										               return (base * R % mod+mod)%mod;
  										           }
  										           else return (R %mod+mod)%mod;
  										       }
  										    static double dis(double x1,double y1,double x2,double y2)
  										    {
  										        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  										    }
  										    static long mod(long x,long y)
  										        {
  										            if(x<0)
  										                x=x+(-x/y+1)*y;
  										            return x%y;
  										        }
  										     public static  long pow(long b, long e) {
  										                long r = 1;
  										                while (e > 0) {
  										                    if (e % 2 == 1) r = r * b ;
  										                    b = b * b;
  										                    e >>= 1;
  										                }
  										                return r;
  										            }
  										    private static void sort(int[] arr) {
  										            List<Integer> list = new ArrayList<>();
  										            for (int object : arr) list.add(object);
  										            Collections.sort(list);
  										        //Collections.reverse(list);
  										            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
  										        }
  										    private static void sort2(long[] arr) {
  										            List<Long> list = new ArrayList<>();
  										            for (Long object : arr) list.add(object);
  										            Collections.sort(list);
  										        Collections.reverse(list);
  										            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
  										        }
  										     static class FastScanner
  								{
  								    private int BS = 1 << 16;
  								    private char NC = (char) 0;
  								    private byte[] buf = new byte[BS];
  								    private int bId = 0, size = 0;
  								    private char c = NC;
  								    private double cnt = 1;
  								    private BufferedInputStream in;
  								 
  								    public FastScanner() {
  								        in = new BufferedInputStream(System.in, BS);
  								    }
  								 
  								    public FastScanner(String s) {
  								        try {
  								            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
  								        } catch (Exception e) {
  								            in = new BufferedInputStream(System.in, BS);
  								        }
  								    }
  								 
  								    private char getChar() {
  								        while (bId == size) {
  								            try {
  								                size = in.read(buf);
  								            } catch (Exception e) {
  								                return NC;
  								            }
  								            if (size == -1) return NC;
  								            bId = 0;
  								        }
  								        return (char) buf[bId++];
  								    }
  								 
  								    public int nextInt() {
  								        return (int) nextLong();
  								    }
  								 
  								    public int[] nextInts(int N) {
  								        int[] res = new int[N];
  								        for (int i = 0; i < N; i++) {
  								            res[i] = (int) nextLong();
  								        }
  								        return res;
  								    }
  								 
  								    public long[] nextLongs(int N) {
  								        long[] res = new long[N];
  								        for (int i = 0; i < N; i++) {
  								            res[i] = nextLong();
  								        }
  								        return res;
  								    }
  								 
  								    public long nextLong() {
  								        cnt = 1;
  								        boolean neg = false;
  								        if (c == NC) c = getChar();
  								        for (; (c < '0' || c > '9'); c = getChar()) {
  								            if (c == '-') neg = true;
  								        }
  								        long res = 0;
  								        for (; c >= '0' && c <= '9'; c = getChar()) {
  								            res = (res << 3) + (res << 1) + c - '0';
  								            cnt *= 10;
  								        }
  								        return neg ? -res : res;
  								    }
  								 
  								    public double nextDouble() {
  								        double cur = nextLong();
  								        return c != '.' ? cur : cur + nextLong() / cnt;
  								    }
  								 
  								    public double[] nextDoubles(int N) {
  								        double[] res = new double[N];
  								        for (int i = 0; i < N; i++) {
  								            res[i] = nextDouble();
  								        }
  								        return res;
  								    }
  								 
  								    public String next() {
  								        StringBuilder res = new StringBuilder();
  								        while (c <= 32) c = getChar();
  								        while (c > 32) {
  								            res.append(c);
  								            c = getChar();
  								        }
  								        return res.toString();
  								    }
  								 
  								    public String nextLine() {
  								        StringBuilder res = new StringBuilder();
  								        while (c <= 32) c = getChar();
  								        while (c != '\n') {
  								            res.append(c);
  								            c = getChar();
  								        }
  								        return res.toString();
  								    }
  								 
  								    public boolean hasNext() {
  								        if (c > 32) return true;
  								        while (true) {
  								            c = getChar();
  								            if (c == NC) return false;
  								            else if (c > 32) return true;
  								        }
  								    }
  								}
  
  										     static class Pair implements Comparable<Pair>{
  										            public long x, y,z;
  										            public Pair(long x1, long y1,long z1) {
  										                x=x1;
  										                y=y1;
  										                z=z1;
  										            }
  										             public Pair(long x1, long y1) {
  										                x=x1;
  										                y=y1;
  										    
  										            }
  										            
  										            @Override
  										            public int hashCode() {
  										                return (int)(x + 31 * y);
  										            }
  										            public String toString() {
  										                return x + " " + y+" "+z;
  										            }
  										            @Override
  										            public boolean equals(Object o){
  										                if (o == this) return true;
  										                if (o.getClass() != getClass()) return false;
  										                Pair t = (Pair)o;
  										                return t.x == x && t.y == y&&t.z==z;
  										            }
  										    public int compareTo(Pair o)
  										    {
  										    			if(x==o.x)
  										    			return (int)(y-o.y);					  	
  										return (int)(x-o.x);
  										     
  										        }
  										     
  										    }
  										}
  										
  										    
  										   
  
  										     
  