Untitled

#include<iostream>

using namespace std;

#define PINK	-1
#define BLUE	1
#define INF		1000000

int N, M;

int gender[100005];

bool check;

int cnt;

int queueS[100005];
int queueE[100005];

int color[100005];

int front, rear;

void Init() {
	check = 0;
	cnt = 0;
	front = rear = 0;

	for (int i = 1; i <= N; i++)
		color[i] = 0;
}

void BFS() {
	int tempA = queueS[front];
	int tempB = queueE[front];
	
	if (gender[tempA] == 1) {
		color[tempA] = 1;
		color[tempB] = 2;
	} else {
		color[tempA] = 2;
		color[tempB] = 1;
	}

	while (front != rear) {
		tempA = queueS[front];
		tempB = queueE[front];
		front++;

		if (color[tempA] == 0 && color[tempB] == 0) {
				queueS[rear] = tempA;
				queueE[rear] = tempB;
				rear++;
			}
			
			if (color[tempA] != 0 && color[tempB] != 0) {
				if (color[tempA] == color[tempB]) {
					check = -1;
					return;
				}
			}
			
			if (color[tempA] != 0 && color[tempB] != 0) {
				if (color[tempA] != color[tempB]) {
					continue;
				}
			}
			
			if (color[tempA] == 0 && color[tempB] != 0) {
				color[tempA] = 3 - color[tempB];
			}
			
			if (color[tempA] != 0 && color[tempB] == 0) {
				color[tempB] = 3 - color[tempA];
			}
	}
}

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

	for (int tc = 1; tc <= T; tc++) {
		cin >> N >> M;

		char temp;
		for (int i = 1; i <= N; i++) {
			cin >> temp;
			gender[i] = temp == 'B' ? 1 : 0;
		}

		Init();

		int a, b;
		for (int i = 0; i < M; i++) {
			cin >> a >> b;
			queueS[rear] = a;
			queueE[rear] = b;
			rear++;
		}

		BFS();
		
		for (int i = 1; i <= N; i++) {
			if (gender[i] == 1) {
				if (color[i] == 2) {
					cnt++;
				}
			}
			
			if (gender[i] == 0) {
				if (color[i] == 1) {
					cnt++;
				}
			}
			
			if (cnt > N - cnt) {
				cnt = N - cnt;
			}
		}


		if (check == -1)
			cout << "-1" << endl;
		else
			cout << cnt << endl;
	}
	return 0;
}