Untitled

#include <iostream>

using namespace std;
int n,m;
char a[100001];
char d[100001];
int b[100001];
int c[100001];
int vs[100001];
int r=-1;
int q[10000000];
int ans,ans1;

void reset()
{
	for(int i=1; i<=n;i++)vs[i]=0;
}
void push(int x)
{
	r++;
	q[r]=x;
}

void pop(int &x)
{
	x=q[r];
	r--;
}

int dfs(int x)
{
	ans1=0;
	int d1=0;
	push(x);
	vs[x]=1;
	while(r!=-1){
		pop(x);
		for(int i=0;i<m;i++){
			if(b[i]==x && vs[c[i]]==0){
				vs[c[i]]=1;
				//push(c[i]);
				
				if(d[b[i]]=='B') d[c[i]]='G';
				else if(d[b[i]]=='G') d[c[i]]='B';

dfs(c[i]);
			}
			else if(c[i]==x && vs[b[i]]==0){
				vs[b[i]]=1;
				//push(b[i]);
				
				if(d[c[i]]=='B') d[b[i]]='G';
				else if(d[c[i]]=='G') d[b[i]]='B';dfs(b[i]);
			}
			else if((b[i]==x && vs[c[i]]==1 && d[c[i]]==d[b[i]])||(c[i]==x && vs[b[i]]==1 && d[c[i]]==d[b[i]])){
				ans1=-1;
				d1=1;
				break;
			}
		}
		if(d1==1) break;
	}
	if(ans1==0){
		for(int i=1; i<=n;i++){
			if(a[i]!=d[i]) ans1++;
		}
	}
	return ans1;
}
int main(){
	freopen("input.txt","r",stdin);
	int t; cin >> t;
	for(int tc = 1; tc <= t; tc++){
		cin >>n>>m; 
		for(int i=1; i<=n; i++){
			cin >> a[i];
		}
		for(int i=1; i<=n; i++){
			vs[i]=0;
		}
		for(int i=0;i<m;i++){
			cin>>b[i]>>c[i];
		}
		r=-1;
		for(int i=0; i<2;i++){
			if(i==0){
				d[1]='G';
				ans=dfs(1);
				reset();
			}
			if(ans!=-1 && i==1){
				d[1]='B';
				if(ans>dfs(1)) ans=dfs(1);
				
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}