#include <chrono>
#include <iostream>
using namespace std;
using namespace std::chrono;
#define opt __attribute((optimize("Ofast")))
#define MAX_STUDENT 100001
#define NO_COLOR 0
#define BLUE 1
#define PINK 2
int T, tc, n, m, f1, f2;
char gender;
bool isBoy[MAX_STUDENT];
int color[MAX_STUDENT];
int inversion;
int wear;
int line = 0;
template <typename TYPE>
class Vector {
public:
TYPE* data;
int size;
int capacity;
Vector() {
size = 0;
capacity = 10;
data = new TYPE[10];
}
void reset() {
size = 0;
capacity = 10;
delete[] data;
data = new TYPE[10];
}
void push(TYPE value) {
if (size == capacity) {
capacity *= 10;
TYPE* temp = new TYPE[capacity];
for (int i = 0; i < size; i++) {
temp[i] = data[i];
}
delete[] data;
data = temp;
}
data[size++] = value;
}
};
class Node {
public:
Vector <int> relation;
int getRelation(int i) { return relation.data[i]; }
} nodes[MAX_STUDENT];
void backtrack(int current, int previousColor) {
if (wear >= n)
return;
if (color[current] == previousColor) {
inversion = -1;
wear = n + 1;
return;
}
else if (color[current] != NO_COLOR)
return;
color[current] = (previousColor == PINK) ? BLUE : PINK;
wear++;
if ((isBoy[current] && color[current] == PINK) || (!isBoy[current] && color[current] == BLUE))
inversion++;
for (int i = 0; i < nodes[current].relation.size; i++) {
backtrack(nodes[current].getRelation(i), color[current]);
}
}
opt int main(int argc, char** argv) { //84ms
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
auto st = high_resolution_clock::now();
cin >> T;
line++;
for (tc = 1; tc <= T; ++tc) {
inversion = 0;
wear = 0;
cin >> n >> m; line++;
//cout << "Size: " << line << " " << n << endl;
line++;
for (int i = 1; i <= n; i++) {
cin >> gender;
if (gender == 'B')
isBoy[i] = true;
else
isBoy[i] = false;
nodes[i].relation.reset();
color[i] = NO_COLOR;
//cout << i << endl;
}
// Relationship
for (int i = 0; i < m; i++) {
cin >> f1 >> f2; line++;
nodes[f1].relation.push(f2);
nodes[f2].relation.push(f1);
}
backtrack(1, BLUE);
if (inversion > (n / 2))
inversion = n - inversion;
if (wear < n) {
inversion = -1;
}
cout << "#" << tc << " " << inversion << endl;
}
auto en = high_resolution_clock::now();
double T = duration_cast<nanoseconds>(en - st).count();
cout << T / 1e9 << endl;
return 0;
}