# HackerEarth 3 types problem solution

In this HackerEarth 3 types problem solution Let's consider some weird country with N cities and M bidirectional roads of 3 types. It's weird because of some unusual rules about using these roads: men can use roads of types 1 and 3 only and women can use roads of types 2 and 3 only. Please answer the following very interesting question: what is a maximum number of roads it's possible to destroy that the country will be still connected for both men and women? A connected country is a country where it's possible to travel from any city to any other using existing roads.

## HackerEarth 3 types of problem solution.

`#include <bits/stdc++.h>using namespace std;int n,m;int a,b,c,ans;int w[1<<20];int get(int x){  if (w[x]==x)    return x;  return w[x]=get(w[x]);}void merge(int a,int b){  w[a]=b;}int W[1<<20][3];int get1(int x,int y){  if (W[x][y]==x)    return x;  return get1(W[x][y],y);}void merge1(int a,int b,int c){  W[a][c]=b;}int main(){ios_base::sync_with_stdio(0);//cin.tie(0);cin>>n>>m;for (int i=1;i<=n;i++)  w[i]=W[i][1]=W[i][2]=i;  for (int i=1;i<=m;i++){  cin>>a>>b>>c;    for (int j=1;j<=2;j++)    if (c&j)    {      int ta,tb;      ta=get1(a,j);      tb=get1(b,j);      if (ta==tb)        continue;      merge1(ta,tb,j);    }      if (c!=3)    continue;  a=get(a);  b=get(b);  if (a==b)    continue;  merge(a,b);  ++ans;}ans=(n-1-ans)*2+ans;int cnt=0;for (int i=1;i<=n;i++)  for (int j=1;j<=2;j++)    if (W[i][j]==i)      ++cnt;      if (cnt>2){  cout<<-1<<endl;  return 0;}cout<<m-ans<<endl;return 0;}`