Untitled

import java.util.Scanner;

public class Solution {
	static int n,m,f,r,inversions;
	static boolean check;
//	static int[][] ke,b;
	static int[] len,a,d,q,g,U,V;
	final static int B = 1,G=2;
	public static void main(String[] args) throws Exception {
//        final long startTime = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
        	n = sc.nextInt();
        	m = sc.nextInt();
        	a = new int[n+1];
        	q = new int[n];
        	d = new int[n+1];
        	U = new int[m];
        	V = new int[m];
        	for(int i=1;i<=n;i++){
        		String s = sc.next();
        		if(s.equals("B")) a[i] = B;
        		else a[i] = G;
        	}
        	for(int i=0;i<m;i++){
        		int u = sc.nextInt();
        		int v = sc.nextInt();
        		U[i] = u;
        		V[i] = v;
        	}
        	check = true;
        	BFS(1);
        	if(check){
	        	inversions = 0;
	        	for(int i=1;i<=n;i++){
	        		if(d[i]!=a[i]) inversions++;
	        	}
	        	inversions = Math.min(inversions, n-inversions);
	        	System.out.println(inversions);
        	}
        	else {
				System.out.println(-1);
			}
        }
//        final long endTime = System.currentTimeMillis();
//        System.out.println("Time: "+(endTime-startTime));
	}
	static void BFS(int u){
		f = 0;r = 0;
		q[r++] = u;
		d[u] = 1;
		while (f<r) {
			int p = q[f++];
			for(int i=0;i<m;i++){
				if(U[i]==p||V[i]==p){
					int j = U[i];
					if(U[i]==p) j = V[i];
					if(d[j]==0){
						d[j] = 3-d[p];
						q[r++] = j;
					}
					else {
						if(d[j]==d[p]){
							check = false;
							return;
						}
					}
				}
			}
		}
	}
}