#include "swap.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pii pair<int, int>
#define ll long long
using namespace std;
const int mxN=100010;
const int mxM=200020;
const int INF=1000000007;
typedef struct line{
int s, e, val;
}line;
int N, M;
vector <line> lin;
vector <pii> col[mxN];
vector <int> Colp[mxN];
bool Chk[mxN];
int Pos[mxN];
int deg[mxN];
bool cmp1(line a, line b)
{
return a.val<b.val;
}
bool cmp2(pii a, pii b)
{
if(a.fir!=b.fir) return a.fir<b.fir;
return a.sec<b.sec;
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
N=n, M=m;
lin.resize(M);
for(int i=0;i<M;i++) lin[i].s=U[i], lin[i].e=V[i], lin[i].val=W[i];
sort(lin.begin(), lin.end(), cmp1);
for(int i=0;i<N;i++) col[i].push_back({0, i});
for(int i=0;i<N;i++) Colp[i].push_back(i);
for(int i=0;i<M;i++)
{
int now1=lin[i].s, now2=lin[i].e, col1, col2;
col1=col[now1].back().sec, col2=col[now2].back().sec;
if(col1==col2)
{
if(Chk[col1]) continue;
for(int ele : Colp[col1])
{
Pos[ele]=i+1;
}
Chk[col1]=true;
continue;
}
bool can;
if(Chk[col1] || Chk[col2]) can=true;
else can=false;
if(can)
{
if(!Chk[col1])
{
for(int ele : Colp[col1]) Pos[ele]=i+1;
Chk[col1]=true;
}
if(!Chk[col2])
{
for(int ele : Colp[col2]) Pos[ele]=i+1;
Chk[col2]=true;
}
}
else
{
if(deg[now1]>=2 || deg[now2]>=2)
{
for(int ele : Colp[col1]) Pos[ele]=i+1;
for(int ele : Colp[col2]) Pos[ele]=i+1;
Chk[col1]=Chk[col2]=true;
}
}
if(Colp[col1].size()<Colp[col2].size())
{
for(int ele : Colp[col1])
{
col[ele].push_back({i+1, col2});
Colp[col2].push_back(ele);
}
}
else
{
for(int ele : Colp[col2])
{
col[ele].push_back({i+1, col1});
Colp[col1].push_back(ele);
}
}
deg[now1]++;
deg[now2]++;
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(col[X].back().sec!=col[Y].back().sec || Pos[X]==0 || Pos[Y]==0) return -1;
int s=0, e=M;
while(s!=e)
{
int mid=(s+e)/2;
pii tmp={mid, INF};
int tmp1=lower_bound(col[X].begin(), col[X].end(), tmp, cmp2)-col[X].begin();
int tmp2=lower_bound(col[Y].begin(), col[Y].end(), tmp, cmp2)-col[Y].begin();
tmp1--;
tmp2--;
if(col[X][tmp1].sec!=col[Y][tmp2].sec) s=mid+1;
else e=mid;
}
e=max(e, max(Pos[X], Pos[Y]));
return lin[e-1].val;
}
