IITKESO207SPA4B - Relaying the roads

no tags 

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.



T in set [1,10]

N in set [1,100]

M in set [1, 10000]


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



hide comments
Programming Club, IITK: 2017-07-15 10:29:48

Hi, we'll change everyone who got 75 to 100 in this assignment. Apologies for the error.

k_kshitiz: 2017-07-14 22:00:56

Tutors should extrapolate those 75/100 to 100/100 for this.

shiwansh: 2017-07-14 19:47:14

i have been stuck with same problem since two days... thanks @djoij123
i would request the concerned people to re-evaluate the test cases for n less than 100

Last edit: 2017-07-14 19:57:01
djoij123: 2017-07-14 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: 2017-07-14 13:16:59

Yes, you will have to output T lines each containing the max roads.

k_kshitiz: 2017-07-12 12:57:00

does the output has T lines each line containing the max roads to be destroyed for each sub-testcase?

Added by:Programming Club, IITK
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)