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 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 i^th character denotes the gender of the i^th 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 Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required.
Else, print "Not possible".

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'

SAMPLE INPUT
3 2
B G B
1 2
1 3

SAMPLE OUTPUT
1

Explanation

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.

Source: hackerearth | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal


Solutions:
def val(x):
	if x=='B':
		return 1
	return 0
n,m=(int(e) for e in input().split())
arr=[val(e) for e in input().split()]
graph={}


for afsafsa in range(m):
	u,v=(int(e)-1 for e in input().split())
	if u in graph:
		graph[u].append(v)
	else:
		graph[u]=[v]
	if v in graph:
		graph[v].append(u)
	else:
		graph[v]=[u]

mem={}
tota_inv=0
def traverse(graph,curr,val):
	global mem
	global total_inv
	if curr not in mem and graph[curr]:
		if arr[curr]!=val:
			total_inv+=1
		mem[curr]=True
		for e in graph[curr]:
			traverse(graph,e,(val+1)%2)

total_inv=0
traverse(graph,0,0)
a=total_inv
mem={}
total_inv=0
traverse(graph,0,1)

print(min(a,total_inv))