Problem: Example

Input

2 1
1 2 2


Output

1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100005
#define MAX_M 100005
typedef pair<int,int> P;

int n,m;
vector<int> group[MAX_N];

vector<int> G[MAX_N];

int x[MAX_M],y[MAX_M],w[MAX_M];

int id[MAX_N];
bool visited[MAX_N];

int c[MAX_N];
vector<int> g[MAX_N];
vector<int> vd;

int dp[MAX_N];

bool dfs(int pos,int prev,int root){
  id[pos]=root;
  visited[pos]=true;
  group[root].push_back(pos);
  
  for(int to:G[pos]){
    if(to==prev)continue;
    if(visited[to])return true;
    if(dfs(to,pos,root))return true;
  }
  return false;
}

bool check(){
  map<P,bool> mp;
  for(int i=0;i<m;i++){
    if(w[i]==1)continue;
    if(x[i]>y[i])swap(x[i],y[i]);
    if(mp[ P(x[i],y[i]) ])return true;
    mp[ P(x[i],y[i]) ]=true;
  }
    
  memset(visited,false,sizeof(visited));
  for(int i=0;i<n;i++){
    if(visited[i])continue;
    if( dfs(i,-1,i) )return true;
  }


  
  for(int i=0;i<m;i++){
    if(w[i]==2)continue;
    int X=id[ x[i] ];
    int Y=id[ y[i] ];
    if(X==Y){
      return true;
    }
    g[X].push_back(Y);
    c[Y]++;
  }

  queue<int> Q;
  for(int i=0;i<n;i++){
    if(c[i]==0&&id[i]==i){
      Q.push(i);
    }
  }

  while(!Q.empty()){
    int pos=Q.front();Q.pop();
    vd.push_back(pos);
    for(int to:g[pos]){
      c[to]--;
      if(c[to]==0)Q.push(to);
    }
  }

  for(int i=0;i<n;i++)
    if(c[i]>0)return true;
  
  return false;
}

int d[MAX_N];
void init(int root){
  root=id[root];
  for(int pos:group[root]){
    d[pos]=-1;
  }
}

void bfs(int root){
  init(root);
  queue<int> Q;
  Q.push(root);
  d[root]=0;
  while(!Q.empty()){
    int pos=Q.front();Q.pop();
    for(int to:G[pos]){
      if(d[to]!=-1)continue;
      d[to]=d[pos]+1;
      Q.push(to);
    }
  }
}

void update(int root,int dif){
  for(int pos:group[root]){
    for(int to:g[pos]){
      dp[to]=max(dp[to],d[pos]+dif+1);
    }
  }
}

int solve(int root){
  int res=0;
  bfs(root);
  int maxm=-1,maxmid;
  for(int pos:group[root])
    if(d[pos]+dp[pos]>maxm)maxm=d[pos]+dp[pos],maxmid=pos;
  
  bfs(maxmid);
  update(root,dp[maxmid]);
  for(int pos:group[root])res=max(res,d[pos]+dp[maxmid]);
  
  maxm=-1;
  for(int pos:group[root])
    if(d[pos]+dp[pos]>maxm)maxm=d[pos]+dp[pos],maxmid=pos;

  bfs(maxmid);
  update(root,dp[maxmid]);
  for(int pos:group[root])res=max(res,d[pos]+dp[maxmid]);
  
  return res;
}

int main(){
  scanf("%d %d",&n,&m);
  for(int i=0;i<m;i++){
    scanf("%d %d %d",&x[i],&y[i],&w[i]);
    x[i]--,y[i]--;
    
    if(w[i]==2){
      G[x[i]].push_back(y[i]);
      G[y[i]].push_back(x[i]);
    }
  }
  
  if( check() ){
    printf("Infinite\n");
    return 0;
  }

  for(int i=0;i<n;i++){
    g[i].clear();
  }
  for(int i=0;i<m;i++){
    if(w[i]==1){
      g[ x[i] ].push_back(y[i]);
    }
  }
  
  int ans=0;
  
  for(int root : vd ){
    if(root!=id[root])continue;
    ans=max(ans,solve(root));
  }
  printf("%d\n",ans);  
  return 0;
}