#include<bits/stdc++.h> using namespace std; int a,b,i,n,m,par[100000],edge[100000],sz[100000]; bool ans[100000]; pair<int, pair<int,int> >p[200000]; int find(int x){ while(x!=par[x]){ x=par[x]; } return x; } bool connect(int a,int b){ if(find(a)==find(b)){ return true; } else{ return false; } } void unite(int a,int b){ edge[a]++; edge[b]++; a=find(a); b=find(b); if(sz[a]<sz[b]){ swap(a,b); } if(edge[a]==3||edge[b]==3||ans[b]==true){ ans[a]=true; } par[b]=a; sz[a]+=sz[b]; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { m=M; n=N; for(i=0;i<M;i++){ p[i].first=W[i]; p[i].second.first=V[i]; p[i].second.second=U[i]; } sort(p,p+m); } int getMinimumFuelCapacity(int X, int Y) { for(i=0;i<100000;i++){ par[i]=i; sz[i]=1; edge[i]=0; } for(i=0;i<m;i++){ unite(p[i].second.first,p[i].second.second); if(connect(X,Y)==true){ if(ans[find(X)]==true||ans[find(Y)]==true){ return p[i].first; } } } return -1; }