Untitled

#include <iostream>

using namespace std;

int N; // number of Students
int M; // number of friendships
int friendship[200002][3], visited[200002];
int gender[100002]; // 1: Boy, 2: Girl
int shirt[100002];  // 1: Blue, 2: Pink
int hasfriend[100000];

char temp;
int ans;
int total;
int temp1;

void DFS(int a, int s)
{
	if(ans == -1) return;
	total++;
	shirt[a] = s;
	if(shirt[a] != gender[a]) temp1++;

	for(int i = 1; i <= 2 * M; i++)
	{
		if(friendship[i][0] == a && visited[i] == 0)
		{
			if(shirt[friendship[i][1]] != 0)
			{
				//cout << friendship[i][0] << " " <<  friendship[i][1];
				ans = -1;
				return;
			}
			else
			{
				visited[i] =1;
				if(friendship[i-1][0] == friendship[i][1] && friendship[i-1][1] == friendship[i][0]) visited[i-1] = 1;
				if(friendship[i+1][0] == friendship[i][1] && friendship[i+1][1] == friendship[i][0]) visited[i+1] = 1;
				DFS(friendship[i][1], 3-s);
			}
		}
	}
}

int main()
{
	//freopen("input1.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++)
	{
		ans = 0;
		cin >> N >> M;
		for(int i = 1; i <= N; i++)
		{
			shirt[i] = 0;
			hasfriend[i] = 0;
			cin >> temp;
			if(temp == 'B') gender[i] = 1;
			else gender[i] = 2;
		}
		for(int i = 1; i <= M; i++)
		{
			cin >> friendship[2*i-1][0] >> friendship[2*i-1][1];
			friendship[2*i][0] = friendship[2*i-1][1];
			friendship[2*i][1] = friendship[2*i-1][0];
			hasfriend[friendship[2*i-1][0]] = 1;
			hasfriend[friendship[2*i-1][1]] = 1;
			visited[2*i-1] =0;
			visited[2*i]= 0; 
		}

		for(int i = 1; i <= N; i++)
		{
			if(hasfriend[i] == 0) shirt[i] = gender[i];
		}

		for(int i = 1; i <= N; i++)
		{
			if(ans == -1) break;
			
			if(shirt[i] == 0) 
			{
				temp1 = 0;
				total = 0;
				DFS(i, 1);
				if(ans == -1) break;
				if(temp1 > total /2) ans = ans + total - temp1;
				else ans = ans + temp1;
				
			}
		}
		cout  << ans << endl;

	}
	return 0;
}