capphatdongkhikhongluduocmang2chieu

#include <iostream>
using namespace std;

int n, m;
char gender[100111];
int a[1000][1000];
// 1 xanh
// 2 do
// 0 chua phat
int check[100111];
int visit[100111];
int ans, dem;
int ok;

int minn(int a, int b) {
	if (a < b) return a;
	return b;
} 


unsigned short int *q[35001];
unsigned short int len[35001], l[35001];
unsigned short int temp[100000][2];

void resetvisit() {
	for (int i = 1; i <= n; i++) {
		visit[i] = 0;
		check[i] = 0;
	}
}

void dfs(int x) {
	if (ok == 1) return;
	visit[x] = 1;

	for (int i = 0; i < len[x]; i++) {
		int tmp = q[x][i];
		if (visit[tmp] == 1) {
			if (check[tmp] == check[x]) {
				//cout << x << " " << i << endl;
				ok = 1;
			}
			
		}
		if (visit[tmp] == 0) {
			
			if (check[x] == 1) {
				check[tmp] = 2;
				if (gender[tmp] == 'B') {
					dem++;
				}
			}
			else {
				check[tmp] = 1;
				if (gender[tmp] == 'G') {
					dem++;
				}
			}
			dfs(tmp);
		}
	}
}

void solve(int testcase) {
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		cin >> gender[i];
		len[i] = 0;
		l[i] = 0;
	}
	
	
	for (int i = 1; i <= m; i++) {
		cin >> temp[i][0] >> temp[i][1];
		len[temp[i][0]]++;
		len[temp[i][1]]++;
	}
	

	for (int i = 1; i <= n; i++) {
		delete[] q[i];
		q[i] = new unsigned short int [len[i] + 1];
	}

	for (int i = 1; i <= m; i++) {
		unsigned int a = temp[i][0], b= temp[i][1];
		q[a][l[a]++] = b;
		q[b][l[b]++] = a;
	}

	dem = 0;
	
	resetvisit();
	check[1] = 1;
	ok = 0;
	if (gender[1] == 'G') {
		dem++;
	}
	dfs(1);
	if (ok == 0) {
		ans = dem;
		dem = 0;
		resetvisit();
		check[1] = 2;
		if (gender[1] == 'B') {
			dem++;
		}
		dfs(1);
		if (ok == 0) {
			ans = minn(ans, dem);
		}
		else {
			ans = -1;
		}
	}
	else {
		ans = -1;
	}
	

	cout << ans << endl;
}

int main() {
	//freopen("Text.txt", "r", stdin);
	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	} 

	return 0;
}