Untitled

import java.util.Scanner;

public class Solution {
	int t, n, m, x, y, front, rear, check, count;
	int arrGioiTinh[];
	int color[];
	int queueStart[];
	int queueEnd[];
	String s;
	Scanner sc = new Scanner(System.in);

	void BFS() {
	int tempx = queueStart[front];
	int tempy = queueEnd[front];
	// front++;
		if (arrGioiTinh[tempx] == 1) {
			color[tempx] = 1;
			color[tempy] = 2;
		} else {
			color[tempx] = 2;
			color[tempy] = 1;
		}
		
		while (front != rear) {
			tempx = queueStart[front];
			tempy = queueEnd[front];
			front++;
			
			if (color[tempx] == 0 && color[tempy] == 0) {
				queueStart[rear] = tempx;
				queueEnd[rear] = tempy;
				rear++;
			}
			
			if (color[tempx] != 0 && color[tempy] != 0) {
				if (color[tempx] == color[tempy]) {
					check = -1;
					return;
				}
			}
			
			if (color[tempx] != 0 && color[tempy] != 0) {
				if (color[tempx] != color[tempy]) {
					continue;
				}
			}
			
			if (color[tempx] == 0 && color[tempy] != 0) {
				color[tempx] = 3 - color[tempy];
			}
			
			if (color[tempx] != 0 && color[tempy] == 0) {
				color[tempy] = 3 - color[tempx];
			}
		}
	}

	void Init() {
		check = 0;
		count = 0;
		front = rear = 0;
		arrGioiTinh = new int[n + 1];
		color = new int[n + 1];
		queueStart = new int[1000000];
		queueEnd = new int[1000000];
	}

	void solution() {
	t = sc.nextInt();
	for (int tc = 1; tc <= t; tc++) {
		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine();
		
		Init();
		for (int i = 1; i <= n; i++) {
			s = sc.next();
			if (s.equalsIgnoreCase("B")) {
				arrGioiTinh[i] = 1;
			}
		}
		
		sc.nextLine();
		for (int i = 0; i < m; i++) {
			x = sc.nextInt();
			y = sc.nextInt();
			queueStart[rear] = x;
			queueEnd[rear] = y;
			rear++;
		}
		
		BFS();
		
		for (int i = 1; i <= n; i++) {
			if (arrGioiTinh[i] == 1) {
				if (color[i] == 2) {
					count++;
				}
			}
			
			if (arrGioiTinh[i] == 0) {
				if (color[i] == 1) {
					count++;
				}
			}
			
			if (count > n - count) {
				count = n - count;
			}
		}
		
		if (check == -1) {
			System.out.println(-1);
		} else {
			System.out.println(count);
		}
	}
	}

public static void main(String[] args) throws Exception {
Solution p = new Solution();
p.solution();

}

}