Starting from:
$30

$24

A10 Solution




Hackerrank Link: ​https://www.hackerrank.com/ooaia-a10-contest




Problem Statement







Let there exist a country with N cities and M bidirectional roads connecting the cities. Each road is either of the following three types.




Passenger transportation road (Type 0) - Only lets the passenger vehicles pass through.



Cargo transportation road (Type 1)- Only lets the cargo vehicles pass through.



Passenger + cargo transportation road (Type 2)- Lets Both passenger and cargo vehicles pass through.



The cities are numbered from 0 to N-1.







We need to find the maximum number of roads that can be closed down, and all the cities still remain connected for both passenger and cargo transportation.




Input Format




N M




///M lines in the following format




<city1 <city2 <roadType







Output Format




A single integer denoting the maximum number of roads that can be closed. If the cities cannot be connected, output -1.




Constraints

1≤N ≤105​

1≤M≤105​




Sample testcases




Input1:




7



0 1 0




1 2 0




1 2 1




1 2 0




1 2 0




0 1 2




0 1 0




Output1:




4




Input2:




6



0 1 0




0 1 1




1 2 1




2 3 1




0 1 2




1 2 0




Output2:




-1

More products