pink_and_blue

 avatar
SSkyFire
java
2 months ago
5.3 kB
0
Indexable
Never
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.



package blue_and_pink;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, friendship;
	static char []a;
	static int []color;
	static int [][]map;
	public static class Queue{
		final int MAX_SIZE = 1000000;
		int []data = new int[MAX_SIZE];
		int front;
		int rear;
		public Queue() {
			front = rear = -1;
		}
		public void init() {
			front = rear = -1;
		}
		public boolean isEmpty() {
			if(front == rear) return true;
			else return false;
		}
		public void enQueue(int element) {
			rear = rear + 1;
			data[rear] = element;
		}
		public int deQueue() {
			front = front + 1;
			return data[front];
		}
	}
	
	static Queue queue;
	
	public static void resetColor() {
		for(int i=0; i<n; i++) {
			color[i] = 0;
		} 
	}
	//1: xanh, 2 hong
	public static int bfs(int start, int mau) {
		queue.init();
		resetColor();
		queue.enQueue(start);
		color[start] = mau;
		boolean check = true;
		while (!queue.isEmpty()) {
			int p = queue.deQueue();
			for(int i=0; i<friendship; i++) {
				if(map[i][0] == p) {
					if(color[map[i][1]] == 0) {
						color[map[i][1]] = 3 - color[p];
						queue.enQueue(map[i][1]);
					}
					else if(color[map[i][1]] == color[p]) {
						check = false;
					}
				}
				else if(map[i][1] == p) {
					if(color[map[i][0]] == 0) {
						color[map[i][0]] = 3 - color[p];
						queue.enQueue(map[i][0]);
					}
					else if(color[map[i][0]] == color[p]) {
						check = false;
					}
				}
			}
			if(check == false) {
				break;
			}
		}
		
		if(check == true) {
			int sumInversion = 0;
			for(int i=1; i<=n; i++) {
				if(a[i] == 'B' && color[i] != 1 || a[i] == 'G' && color[i] != 2) {
					sumInversion ++;
				}
			}
			return sumInversion;
		}
		else {
			return -1;
		}
	}
	
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("src/blue_and_pink/input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int TC = sc.nextInt();
		queue = new Queue();
		for(int t=0; t<TC; t++) {
			n = sc.nextInt();
			friendship = sc.nextInt();
			a = new char[n+1];
			color = new int[n+1];
			map = new int[friendship][2];
			
			for(int i=1; i<=n; i++) {
				a[i] = sc.next().charAt(0);
			}
			
			for(int i=0; i<friendship; i++) {
				map[i][0] = sc.nextInt();
				map[i][1] = sc.nextInt();
			}
			
			int minInversion = Integer.MAX_VALUE;
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=2; j++) {
					int res = bfs(i, j);
					if(res != -1 && res < minInversion) {
						minInversion = res;
					}
				}
			}
			if(minInversion == Integer.MAX_VALUE) {
				System.out.println(-1);
			}
			else {
				System.out.println(minInversion);
			}
			
		}
	}
}
Leave a Comment