PinkAndBlue

Pink and Blue
Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy.

Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition:

Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa.

Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion.

So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task.

Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation.

 

Input
The first line is the number of test cases T.

First line of each test case contains 2 space-separated integers - N and M - number of students and number of friendships present respectively.

Second line consists of N space-separated characters, where ith character denotes the gender of the ith student. B: Boy, G: Girl.

M lines follow. Each line consists of 2 space-separated integers, u and v, showing that u is a friend of v and vice-versa.

 

Output
If Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required.
Else, print -1.

 

Constraints
1 ≤ N ≤ 105
1 ≤ M ≤ 105
1 ≤ u, v ≤ N

Colors of T-Shirt are represented by uppercase characters 'B' and 'G'

 

Sample

 

Input

3

3 2

B G B

1 2

1 3

6 9

B B B G G G

3 5

2 6

4 2

6 3

3 1

3 4

6 1

5 1

1 4

6 5

G G G B G G

6 3

1 3

2 3

4 3

5 3

 

Output 

1

-1

2

 

Explanation

#1

Student 1 can be given a Blue T-Shirt. Hence, Student 2 and 3 would receive Pink T-Shirts. Since, Student 3 is a Boy and has received a Pink T-Shirt, number of inversions = 1.

#include<iostream>
using namespace std;
#define pii pair<int,int>
#define piii pair<pii,int>
const int mn =1e5+6;
const int maxS = 2e6+6;

template <typename T>
class Vector{
private:
	int size;
	int capacity;
	T *array;
	void expand(int newCapacity)
	{ 
	    if (newCapacity <= size)
	        return;
	
	    T * old = array; 
	    array = new T[newCapacity];
	    
	    for (int i = 0; i < size; i++)
	        array[i] = old[i];
	    
		delete[] old;
	    capacity = newCapacity;
	}
public:
	Vector(int initCapacity = 1)
	{
	    size = 0;
	    capacity = initCapacity;
	    array = new T[capacity];
	}
	~Vector() 
	{
	    delete[] array;
	}
	Vector & operator=(Vector & rhs) 
	{
	    if (this != &rhs)
		{
	        delete[] array;
	        size = rhs.size;
	        capacity = rhs.capacity;
	        array = new T[capacity];
	        for (int i = 0; i < size; i++)
	            array[i] = rhs.array[i];
	    }
	    
	    return *this;
	}
	int Size() 
	{
	    return size;
	}
	T & operator[](int index) 
	{
	    return array[index];
	}
	void push_back(T newElement) 
	{
	    if (size == capacity)
	        expand(2 * size);
	    array[size] = newElement;
	    size++;
	}
	void popBack() 
	{
	    size--;
	}
	void clear() 
	{
	    size = 0;
	}
};
Vector<int> g[mn];
char a[mn];
int no[mn],dx[mn],dy[mn],xet[mn];
int n,m,dem1,dem2,res,check;
void dfs(int x)
{
	for(int i=0;i<g[x].Size();i++)
	{
		int y=g[x][i];
		if(xet[y]==xet[x]){check=1;break;}
		if(xet[y]!=0)continue;
		if(check==0)
		{
			xet[y]=3-xet[x];
			if(xet[y]==1&&a[y]=='G')dem1++;
			if(xet[y]==2&&a[y]=='B')dem1++;
			if(xet[y]==1&&a[y]=='B')dem2++;
			if(xet[y]==2&&a[y]=='G')dem2++;
			dfs(y);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen("1.txt","r",stdin);
	//freopen(".out","w",stdout);
	int te=10;
	cin>>te;
	for(int tes=1;tes<=te;tes++)
	{
		//cout<<"Case "<<tes<<"\n";
		res=0;
		check=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			g[i].clear();
			xet[i]=0;
		}
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		for(int i=1;i<=n;i++)
			if(xet[i]==0)
				{
					dem1=dem2=0;
					xet[i]=1;
					if(xet[i]==1&&a[i]=='G')dem1++;
					if(xet[i]==2&&a[i]=='B')dem1++;
					if(xet[i]==1&&a[i]=='B')dem2++;
					if(xet[i]==2&&a[i]=='G')dem2++;
					dfs(i);
					if(dem1<dem2)res+=dem1;
					else res+=dem2;
			}
			//for(int i=1;i<=n;i++)cout<<xet[i]<<" ";
		if(check)cout<<-1<<'\n';
		else cout<<res<<'\n';
	}
	return 0;
}