Pink and Blue 100/100

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 M 100000

int qux[1000000], quy[1000000];
int n, m, f, r;
int **a, visit[100005];
int temp[100005][2];
int gt[100005], mau[100005];
int number[100005], dem[100005];
int ketqua;
void Init()
{
	f = r = 0;
	for(int i = 1; i <= n; i++)
			 visit[i] = 0;
}
int BFS()
{
	Init();

	qux[r] = 1;
	//quy[r] = 1;
	r++;
	visit[1] = 1;

	int temp;
	while(f != r)
	{
		temp = qux[f];
		f++;

		for(int i = 1; i<= number[temp]; i++)
		{
			int next = a[temp][i];
			if( visit[next] == 0)
			{
				visit[next] = 1;
				mau[next] = 1 - mau[temp];
				if(mau[next] != gt[next]){
					ketqua++;
				}
				qux[r++] = next;
			}else{
				if(mau[next] == mau[temp]){
					return -1;
				}
			}
		}
	}
	return ketqua;
}
int main()
{
	int T;
	//freopen("input.txt","r", stdin);
	//freopen("output.txt","w", stdout);
	cin>>T;
	for(int tc=1;tc<=T;tc++){
		ketqua = 0;
		cin >>n >> m;

		for(int i = 1; i <= n; i++){
			number[i] = 0;
			mau[i] = -1;
		}
		char buff;
		for(int i= 1; i <= n; i++){
			cin >> buff;
			if(buff == 'B'){
				gt[i] = 1;
			}else{
				gt[i] = 0;
			}
		}
		int x, y;
		a = new int*[n+1];
		for(int i = 0; i < m; i++)
		{
			cin >> x >> y;
			//cout<<x<<":"<<y<<endl;
			number[x]++;
			number[y]++;
			temp[i][0] = x;
			temp[i][1] = y;
		}
		for(int i=1;i<=n;i++){
			a[i] = new int[number[i]];
			dem[i] = 0;
		}
		for(int i = 0; i < m; i++)
		{
			x = temp[i][0];
			y = temp[i][1];
			dem[x]++;
			dem[y]++;
			a[x][dem[x]] = y;
			a[y][dem[y]] = x;
		}
		//BFS///
		mau[1] = gt[1];
		int result1 = BFS();
		int result2 = n - result1;
		if(result1>result2){
			cout<<result2<<endl;
		}else{
			cout<<result1<<endl;
		}
		
	}
	

}