CS2810 OOAIA: A10

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment || To Order Original Work Click Custom Order?

Description

5/5 - (3 votes)

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

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