IITKESO207SPA4B  Relaying the roads
A city contains 3 types of roads (1, 2 and 3) which join the sectors of the city. Road type1 is used by two wheelers only, road type 2 is used by four wheelers only and road
type 3 is used by both. The mayor need to destroy some roads so as to reduce the expense on maintenance of roads. What is the
maximum number of roads that can be destroyed such that the city will be still connected for both X and Y
A connected city is one where it is possible to travel from any sector to any other using existing roads. All the roads are bidirectional.
Input format
The first line will contain a single integer T, denoting the number of test cases. Each test case will consist of first, a line containing two integers N and M which denote the number of sectors and the number of roads. The next M lines will contain three space seperated integers indicating the two sectors that are joined and the road type.
Output format
A single integer, which dentoes the maximum number of roads you can destroy.
Constrains
T in set [1,10]
N in set [1,100]
M in set [1, 10000]
Sample input
1
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
hide comments
Programming Club, IITK:
20170715 10:29:48
Hi, we'll change everyone who got 75 to 100 in this assignment. Apologies for the error. 

k_kshitiz:
20170714 22:00:56
Tutors should extrapolate those 75/100 to 100/100 for this. 

shiwansh:
20170714 19:47:14
i have been stuck with same problem since two days... thanks @djoij123


djoij123:
20170714 19:44:08
if someone is getting 75 marks try changing the limit of N from 100 to 1000, the constrain given is WRONG. 

Programming Club, IITK:
20170714 13:16:59
Yes, you will have to output T lines each containing the max roads. 

k_kshitiz:
20170712 12:57:00
does the output has T lines each line containing the max roads to be destroyed for each subtestcase? 
Added by:  Programming Club, IITK 
Date:  20170706 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 