Dr. Viru Sahastrabuddhe was a strict professor and he had N students. The N student were sitting in a room. Each student 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 Dr. Viru Sahastrabuddhe. This made the students very happy. Dr. Viru Sahastrabuddhe 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, Dr. Viru Sahastrabuddhe 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, Dr. Viru Sahastrabuddhe 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.

Constraints:
1 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
1 ≤ u, v ≤ N
Colours of T-Shirt are represented by uppercase characters ‘B’ and ‘G’

Input Format:
First line 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 Format:
If Dr. Viru Sahastrabuddhe could distribute the T-Shirts in the desired way, print the minimum number of inversions required.
Else, print “Not possible”.

Logical Test-Case 1 →
INPUT:
8 5
B B G B G G B G
2 4
1 3
4 2
3 1
5 2

OUTPUT:
2

#include <stdio.h>
#include <stdlib.h>
// need to find if the graph is bi-partite.
// if it is then there are two ways to color it since there is only one connected component
#define WHITE 2
#define PINK 1
#define BLUE 0
#define BOY 0
#define GIRL 1

typedef struct node {
int vertex;
struct node* next;
}node_t;

int* colour;
int* gender;
int i;

int findInversions( int n ) {
int* queue = (int*)calloc(n,sizeof(int));
int queueStart = n-1;
int queueEnd = n-1;
queue[n-1] = 0; // 0 is the source vertex;
colour[0] = BLUE; // arbitrary
while( queueStart<=queueEnd ) {
int vertex = queue[queueEnd–];
while(t!=NULL) {
int v2 = t->vertex;
if( colour[v2] == WHITE ) {
colour[v2] = 1- colour[vertex];
queue[–queueStart] = v2;
}
else {
if(colour[v2] == colour[vertex])
return -1;
}
t=t->next;
}
}
// coming here means that coloring is possible
// now count the inversions in this coloring
int count =0;
for(i=0;i<n;i++) {
if(colour[i] != gender[i])
count ++;
}
if( count > n/2 )
count = n-count;
return count;
}

int main()
{
int n,m,v1,v2;
char* temp;
scanf("%d%d", &n, &m);
temp=(char*)calloc(4,sizeof(char));
colour=(int*)calloc(n,sizeof(int));
gender=(int*)calloc(n,sizeof(int));
for(i=0;i<n;i++) {
scanf("%s", temp);
if(temp[0] == ‘B’)
gender[i] = BOY;
else
gender[i] = GIRL;
colour[i] = WHITE;
}
for(i=0;i<m;i++) {
scanf("%d%d", &v1, &v2);
v1–;v2–; // 0 based indexing
node_t* t = (node_t*)malloc(sizeof(node_t));
t->vertex = v2;

``````	t = (node_t*)malloc(sizeof(node_t));
t->vertex = v1;