pink_blue

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;

void Init();
void Solve();

int main(void)
{
  //freopen("input.txt", "r", stdin);

  int T;
  cin >> T;

  for (int i = 1; i <= T; i += 1)
  {
    Init();
    Solve();
  }

  return 0;
}

int N, M;
int ListLen[100006];
int mListLen[100006];
int mColor[100006];
int Color[100006];
int **List;
int Edges[100006][2];


void Init()
{
  cin >> N >> M;

  for (int i = 1; i <= N; i += 1)
  {
    ListLen[i] = 0;
    mListLen[i] = 0;
    mColor[i] = -1;
  }

  List = new int * [N + 1];

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

  int u, v;
  for (int i = 0; i < M; i += 1)
  {
    cin >> u >> v;
    Edges[i][0] = u;
    Edges[i][1] = v;

    mListLen[u] += 1;
    mListLen[v] += 1;
  }

  for (int i = 1; i <= N; i += 1)
  {
    List[i] = new int[mListLen[i]];
  }

  for (int i = 0; i < M; i += 1)
  {
    u = Edges[i][0];
    v = Edges[i][1];

    ListLen[u] += 1;
    ListLen[v] += 1;

    List[u][ListLen[u]] = v;
    List[v][ListLen[v]] = u;
  }
}

int BFS();

void Solve()
{
  mColor[1] = Color[1];

  int res1 = BFS();
  int res2 = N - res1;

  if (res1 > res2)
  {
    cout << res2 << endl;
  }
  else
  {
    cout << res1 << endl;
  }
}

int Queue[10000001];
int FrontQ, RearQ;

void PushQ(int);
int PopQ();

bool Visited[100006];

int BFS()
{
  for (int i = 1; i <= N; i += 1)
    Visited[i] = 0;

  FrontQ = RearQ = -1;

  PushQ(1);
  Visited[1] = 1;

  int cnt = 0;

  while (FrontQ != RearQ)
  {
    int u = PopQ();

    for (int i = 1; i <= ListLen[u]; i += 1)
    {
      int v = List[u][i];
      if (!Visited[v])
      {
        Visited[v] = 1;
        mColor[v] = 1 - mColor[u];

        if (mColor[v] != Color[v])
          cnt += 1;

        PushQ(v);
      }
      else
      {
        if (mColor[v] == mColor[u])
          return -1;
      }
    }
  }

  return cnt;
}

void PushQ(int x)
{
  RearQ += 1;
  Queue[RearQ] = x;
}

int PopQ()
{
  FrontQ += 1;
  return Queue[FrontQ];
}