pinkandbluequoc

#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;
} 

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 = 1; i <= n; i++) {
		if (visit[i] == 1 && a[x][i] == 1) {
			if (check[i] == check[x]) {
				//cout << x << " " << i << endl;
				ok = 1;
			}
			
		}
		if (visit[i] == 0 && a[x][i] == 1) {
			
			if (check[x] == 1) {
				check[i] = 2;
				if (gender[i] == 'B') {
					dem++;
				}
			}
			else {
				check[i] = 1;
				if (gender[i] == 'G') {
					dem++;
				}
			}
			dfs(i);
		}
	}
}

void solve(int testcase) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			a[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> gender[i];
	}
	
	
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		a[u][v] = 1;
		a[v][u] = 1;
	}
	
	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 << "#" << testcase << " " << ans << endl;
}

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

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

	return 0;
}