pinkandbluesol

#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, lan1, lan2;
int ok;

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;
			}
		}
		if (visit[i] == 0 && a[x][i] == 1) {
			
			if (check[x] == 1) {
				check[i] = 2;
			}
			else {
				check[i] = 1;
			}
			dfs(i);
		}
	}
}

void solve(int testcase) {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> gender[i];
	}
	
	int ok = 0;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		a[u][v] = 1;
		a[v][u] = 1;
	}
	lan1 = 0;
	check[1] = 1;
	ok = 0;
	resetvisit();
	dfs(1);
	
	if (ok == 1) {
		cout << "quoc" << endl;
	}
	for (int i = 1; i <= n; i++) {
		cout << check[i] << " ";
	}
	cout << endl;
	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;
}


#include <iostream>

using namespace std;


const int oo = 99999999;



struct custom{
	unsigned short int *arr;
	int size;
};

custom mtk[100003];
int gender[100003];
int visit[3][100003];
short dem[100003];


int sizee(int node)
{
	return mtk[node].size;
}

void pushh(int node, int v)
{
	mtk[node].arr[++mtk[node].size] = v;
}

int pull(int node, int pos)
{
	return mtk[node].arr[pos];
}


void reset_init(int n)
{
	for (int i = 0; i<=n+1; i++)
	{
		mtk[i].size = 0;
		delete[] mtk[i].arr;
		mtk[i].arr = new unsigned short int[dem[i] + 2];
	}
}

int n, m;
int kt[2];
int ans[2];

struct point
{
	unsigned short int x;
	unsigned short int y;
};

point tmpip[1000003];

void DFS(int index, int uu, int color)
{
	visit[index][uu] = color;
	if (gender[uu] != color) ans[index] += 1;
	if (kt[index] == 1)  return;
	
	int sizeuu = sizee(uu);
	int newcolor = color*(-1);
	for (int j  = 1; j<=sizeuu; j++)
	{
		int node = pull(uu, j);
		if (visit[index][node] != 0)
		{
			if (visit[index][node] == color)
				kt[index] = 1;
		} else
			DFS(index, node, newcolor);
	}
}
int main()
{
	//freopen("inpu.txt","r",stdin);
	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{
		cin >> n >> m;
		//cout << tc;
		for (int i = 1; i <= n; i++)
		{
			dem[i] = 0;
			visit[0][i] = 0;
			visit[1][i] = 0;
			char tm;
			cin >> tm;
			gender[i] = (tm == 'B'? 1 : -1);
		}

		for (int i = 1; i <= m; i++)
		{
			int u, v;
			cin >> u >> v;
			dem[u]++;
			dem[v]++;
			tmpip[i].x = u;
			tmpip[i].y = v;
		}
		reset_init(n);

		int max = 0;
		for (int i = 1; i <= n; i++)
			if (dem[i] > 0)
			{
				//cout << dem[i] << " ";
				if (dem[i] > max) max = dem[i];
			}

		for (int i = 1; i <= m; i++)
		{
			pushh(tmpip[i].x, tmpip[i].y);
			pushh(tmpip[i].y, tmpip[i].x);
		}

		

		kt[0] = 0; ans[0] = 0;
		kt[1] = 0; ans[1] = 0;
		// luot 0, nguoi 1, mac ao mau 1(xanh), doidadaonguoc = 0;
		DFS(0, 1, 1);
		DFS(1, 1, -1);

		if (kt[0] == true && kt[1] == true)
		{
			cout << -1 <<endl;
		} else if (kt[0] == false && kt[1] == false)
		{
			cout << (ans[0] < ans[1] ? ans[0] : ans[1]) << endl;
		} else if (kt[1] == false)
			cout << ans[0] << endl;
		else cout << ans[1] << endl;
		
	}
	return 0;
}