Description
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
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 ≤ 10
5
1 ≤ M ≤ 10
5
Sample testcases
Input1:
3 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:
4 6
0 1 0
0 1 1
1 2 1
2 3 1
0 1 2
1 2 0
Output2:
-1
