Solved-A10- Solution

Description

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

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:

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