/*******************
* what the sigma *
********************/
#include <iostream>
#include <vector>
#include <map>
#include <chrono>
#include <set>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
bool enabledb=0;
#define DB(CODE) cout<<'\t'<<CODE<<endl;
#define SP <<' '<<
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define tll tuple<ll,ll,ll>
#define sz(x) ((int)x.size())
#define pb push_back
const ll mod = 1e9+7,maxn=300005;
const ll INF=(ll)9e18;
struct pDSU{
ve<int> pa;
ve<int> szz;
ve<int> tpa;
ve<int> tdeg3;
ve<int> tcyc;
ve<int> deg;
pDSU(int N):pa(N),szz(N),tpa(N),tdeg3(N),deg(N),tcyc(N){
for (int i=0;i<N;i++) {
pa[i]=i;
szz[i]=1;
tpa[i]=-1;
tcyc[i]=-1;
tdeg3[i]=-1;
deg[i]=0;
}
}
int find(int u,int time) {
if (tpa[u]!=-1&&tpa[u]<=time) {
return find(pa[u],time);
}
return u;
}
void unite(int u,int v,int time) {
deg[u]++;
deg[v]++;
bool b=(deg[u]>=3||deg[v]>=3);
int x=find(u,time);
int y=find(v,time);
if (x==y) {
if (tcyc[x]==-1) {
tcyc[x]=time;
}
if (tdeg3[x]==-1&&b) {
tdeg3[x]=time;
}
} else {
if (szz[x]<szz[y]) {
swap(x,y);
}
pa[y]=x;
if (tdeg3[y]!=-1&&tdeg3[x]==-1) {
tdeg3[x]=time;
}
if (tcyc[y]!=-1&&tcyc[x]==-1) {
tcyc[x]=time;
}
szz[x]+=szz[y];
tpa[y]=time;
if (b&&tdeg3[x]==-1) {
tdeg3[x]=time;
}
}
}
int query(int u,int time) {
u=find(u,time);
int ans=tdeg3[u];
if (tcyc[u]!=-1) {
if (ans==-1) {
ans=tcyc[u];
} else {
ans=min(ans,tcyc[u]);
}
}
return ans;
}
int gettime(int u,int v) {
int l=0,r=1e9;
while (l<=r) {
int mid=(l+r)>>1;
int x=find(u,mid);
int y=find(v,mid);
if (x==y) {
r=mid-1;
} else {
l=mid+1;
}
}
return l;
}
}DSU(maxn);
void init(int N, int M,ve<int> U,ve<int> V,ve<int> W) {
int n=N;
int m=M;
ve<tii> edges;
for (int i=0;i<m;i++) {
edges.pb({W[i],U[i],V[i]});
}
sort(be(edges));
for (auto [w,u,v]:edges) {
DSU.unite(u,v,w);
}
}
ll getMinimumFuelCapacity(int X,int Y) {
int time=DSU.gettime(X,Y);
X=DSU.find(X,time);
while (DSU.tpa[X]!=-1&&DSU.tcyc[X]==-1&&DSU.tdeg3[X]==-1) {
time=DSU.tpa[X];
X=DSU.pa[X];
}
if (DSU.tcyc[X]==-1&&DSU.tdeg3[X]==-1) return -1;
int tim2=1e9;
if (DSU.tcyc[X]!=-1) {
tim2=min(tim2,DSU.tcyc[X]);
}
if (DSU.tdeg3[X]!=-1) {
tim2=min(tim2,DSU.tdeg3[X]);
}
time=max(time,tim2);
return time;
}
