#include"swap.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
// general
ll const MXN = 100005;
ll const INF = 1e13;
ll n, m;
vector<pii> edgeslist;
bool compare(pii a, pii b)
{
return a.f<b.f;
}
// persistent UFDS with union by rank
vector<pi> par[MXN], siz[MXN], mxdeg[MXN], cntedge[MXN];
ll deg[MXN];
ll timetravel(vector<pi>& arr, ll time)
{
ll ind = ub(arr.begin(), arr.end(), mp(time, INF))-arr.begin()-1;
return arr[ind].s;
}
ll find(ll node, ll time)
{
ll p = timetravel(par[node], time);
return (p!=node)?find(p, time):p;
}
void unite(ll x, ll y, ll t)
{
deg[x]++; deg[y]++;
ll px = find(x,t), py = find(y, t);
if (px==py)
{
mxdeg[px].pb(mp(t, max(mxdeg[px].back().s, max(deg[x], deg[y]))));
cntedge[px].pb(mp(t, cntedge[px].back().s+1));
}
else
{
if (siz[px].back().s<siz[py].back().s) swap(px, py);
par[py].pb(mp(t, px));
siz[px].pb(mp(t, siz[px].back().s+siz[py].back().s));
mxdeg[px].pb(mp(t, max(max(mxdeg[px].back().s, mxdeg[py].back().s), max(deg[x], deg[y]))));
cntedge[px].pb(mp(t, cntedge[px].back().s+1 +cntedge[py].back().s ));
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n =N, m=M;
for (ll i=0; i<n; ++i)
{
par[i].pb(mp(-1, i));
siz[i].pb(mp(-1, 1));
mxdeg[i].pb(mp(-1, 0));
cntedge[i].pb(mp(-1, 0));
deg[i] = 0;
}
edgeslist.resize(m);
for (ll i=0; i<m; ++i) edgeslist[i] = mp(W[i], mp(U[i], V[i]));
sort(edgeslist.begin(), edgeslist.end(), compare);
ll time = -1;
for (pii e: edgeslist) unite(e.s.f, e.s.s, ++time);
}
int getMinimumFuelCapacity(int X, int Y)
{
ll x = X, y= Y, lo = 0, hi = m;
while (lo!=hi)
{
ll mid = (lo+hi)/2;
ll px = find(x, mid), py = find(y, mid);
if ((px==py) && ((timetravel(mxdeg[px], mid)>2) || (timetravel(cntedge[px], mid)>timetravel(siz[px], mid)-1))) hi = mid;
else lo = mid+1;
}
return (lo==m)?-1: edgeslist[lo].f;
}
