3-types

Russian translation

Let's consider some weird country with N cities and M bidirectional roads of 3 types. It's weird because of some unusual rules about using these roads: men can use roads of types 1 and 3 only and women can use roads of types 2 and 3 only. Please answer the following very interesting question: what is maximum number of roads it's possible to destroy that the country will be still connected for both men and women? Connected country is country where it's possible to travel from any city to any other using existing roads.

Input

The first line contains 2 space-separated integer: N and M. Each of the following M lines contain description of one edge: three different space-separated integers: a, b and c. a and b are different and from 1 to N each and denote numbers of vertices that are connected by this edge. c denotes type of this edge.

Output

For each test case output one integer - maximal number of roads it's possible to destroy or -1 if the country is not connected initially for both men and women.

Constraints 
1 ≤ N ≤ 1000
1 ≤ M ≤ 10 000
1 ≤ a, b ≤ N
1 ≤ c ≤ 3

SAMPLE INPUT
5 7
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
5 2 2
1 5 1


SAMPLE OUTPUT
2

Difficulty: MEDIUM

Starter code:

Solutions:
class Vertex(object):
	rank = 0

	def __init__(self, label):
		self.label = label
		self.p = self

	def __repr__(self):
		return "{}".format(self.label)


class Edge(object):
	def __init__(self, u, v, w):
		self.u = u
		self.v = v
		self.w = w

	# def __cmp__(self, e):
	# return -1 if self.w < e.w else 1 if self.w > e.w else 0

	def __repr__(self):
		return "({}, {};{})".format(self.u, self.v, self.w)


def union(x, y):
	link(find_set(x), find_set(y))


def link(x, y):
	if x.rank > y.rank:
		y.p = x
	else:
		x.p = y
		if y.rank == x.rank:
			y.rank += 1


def find_set(x):
	if x != x.p:
		x.p = find_set(x.p)
	return x.p


def kruskal(vertices, edges):
	mst = set()
	edges.sort(key=lambda x: x.w)
	for e in edges:
		if find_set(e.u) != find_set(e.v):
			mst.add((e.u.label, e.v.label))
			union(e.u, e.v)
	return mst


def main():
	n, m = list(map(int, input().split()))
	vertices = []
	# edges = []
	roads_for_men = []
	roads_for_woman = []

	for i in range(n):
		vertices.append(Vertex(i))

	for i in range(m):
		u, v, t = list(map(int, input().split()))
		# edges.append(Edge(vertices[u - 1], vertices[v - 1], t))
		if t == 3:
			roads_for_men.append(Edge(vertices[u - 1], vertices[v - 1], 0))
			roads_for_woman.append(Edge(vertices[u - 1], vertices[v - 1], 0))
		elif t == 2:
			roads_for_woman.append(Edge(vertices[u - 1], vertices[v - 1], 1))
		elif t == 1:
			roads_for_men.append(Edge(vertices[u - 1], vertices[v - 1], 1))

	mstw = kruskal(vertices, roads_for_woman)
	for v in vertices:
		v.rank = 0
		v.p = v
	mstm = kruskal(vertices, roads_for_men)
	if len(mstw) < (n-1) or len(mstm) < (n-1):
		print((-1))
	else:
		print(m - len(mstm.union(mstw)))



if __name__ == '__main__':
	main()
	#
	# p = Vertex(1)
	# q=Vertex(2)
	# print(find_set(p)==find_set(q))


from collections import defaultdict

def make_set(N):
	global parents
       
	for node in range(1,N+1):
	    parents[node] = node
	    
	    
def Union(node1,node2):
	global parents
	   
	node1_root = Find(node1)
	node2_root = Find(node2)

	if node1_root == node2_root:
	     return
	
	parents[node1_root] = node2_root

	
	    
def Find(node):
	global parents
	if parents[node] != node:
	    parents[node] = Find(parents[node])    
	return parents[node]




def Krushkal(weighted_edge_list=[],N=0):
     
	count_edges = 0
	gender_edges   = 0
	
	make_set(N)
	weighted_edge_list.sort(key=lambda x:x[2],reverse=True)
      
	for edge in weighted_edge_list:
	    
	    root1 = Find(edge[0])
	    root2 = Find(edge[1])
	
	    if root1 != root2:
		Union(root1,root2)
		count_edges += 1
		if (edge[2] == 1)  or (edge[2] ==2):
		    gender_edges+=1
		
	      
	    if count_edges == N-1:
		 break


	
		
	if count_edges == N-1:
	    return [True ,gender_edges]
	else:
	    return [False,gender_edges]


t = 1

while t>0:
    N,M    = [int(x) for x in input().split()]
    parents = [0]*10**6
    
    men     = []
    women   = []
    result  = 0

    for i in range(M):
	node = [int(x) for x in input().split()]
	if node[2]==3:
	    men.append(node)
	    women.append(node)
	elif node[2] == 2:
	    women.append(node)
	else:
	    men.append(node)
	

    
    ans = Krushkal(men,N)
    if ans[0]:
	result +=ans[1]
	parents = [0]*10**6
	
	ans     = Krushkal(women,N)
	if ans[0]:
	    result+=ans[1]
	    print(M-(N-1-ans[1]+result))
	else:
	    print(-1)
    else:
	print(-1)
    

    t -= 1


import collections
import heapq

def mst(graph, n):
	total = 0
	seen_m = set([1])
	seen_f = set([1])
	q = graph[1]
	heapq.heapify(q)
	while q:
		used = False
		kind, node = heapq.heappop(q)
		# if node in seen_m and node in seen_f: continue
		if kind in (-1, -3) and node not in seen_m:
			seen_m.add(node)
			used = True
		if kind in (-2, -3) and node not in seen_f:
			seen_f.add(node)
			used = True
		if not used: continue
		total += 1
		if len(seen_m) == n and len(seen_f) == n: break
		for child in graph[node]:
			heapq.heappush(q, child)
	if len(seen_m) != n or len(seen_f) != n: return -1
	return total

def solve(n, mss):
	graph = collections.defaultdict(list)
	for a, b, kind in mss:
		graph[a].append((-kind, b))
		graph[b].append((-kind, a))
	mini = mst(graph, n)
	if mini == -1: return -1
	return len(mss) - mini

if __name__ == '__main__':
	n, m = list(map(int, input().split()))
	mss = [list(map(int, input().split())) for _ in range(m)]
	print(solve(n, mss))