#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
typedef long double ld;
typedef long long ll;
const int bucketsize = 1000;
const int obsize = 200000 / bucketsize;
//#define int long long
struct DSU
{
vector<int> deg, parent, siz;
vector<int> cdeg, cparent, csiz;
vector<char> maxdeg, cmaxdeg;
vector<int> modif;
vector<bool> apare, earb, cearb;
void init(int n)
{
deg.resize(n);
siz.resize(n);
parent.resize(n);
maxdeg.resize(n);
apare.resize(n);
earb.resize(n);
for (int i = 0; i < n; i++)
{
parent[i] = i;
siz[i] = 1;
maxdeg[i] = deg[i] = 0;
apare[i] = 0;
earb[i] = 1;
}
}
void seteaza()
{
cdeg = deg;
cmaxdeg = maxdeg;
cparent = parent;
csiz = siz;
cearb = earb;
for (auto u : modif)
apare[u] = false;
modif.clear();
}
void reset()
{
//cerr<<"resetez\n"<<modif.size()<<"\n\n";
for (auto u : modif)
{
apare[u] = false;
parent[u] = cparent[u];
siz[u] = csiz[u];
deg[u] = cdeg[u];
maxdeg[u] = cmaxdeg[u];
earb[u] = cearb[u];
//cerr<<" dupa resetare siz "<<u<<" -> "<<siz[u]<<'\n';
}
modif.clear();
}
int cauta(int u)
{
if (u == parent[u])
return u;
if (apare[u] == 0) apare[u] = 1, modif.push_back(u);
return parent[u] = cauta(parent[u]);
}
void unite(int u, int v)
{
deg[u]++;
deg[v]++;
if (apare[u] == 0) apare[u] = 1, modif.push_back(u);
if (apare[v] == 0) apare[v] = 1, modif.push_back(v);
int cu = cauta(u);
int cv = cauta(v);
maxdeg[cu] = max(maxdeg[cu], (char)min(3, deg[u]));
maxdeg[cv] = max(maxdeg[cv], (char)min(3, deg[v]));
u = cu;
v = cv;
if (apare[cu] == 0) apare[cu] = 1, modif.push_back(cu);
if (apare[cv] == 0) apare[cv] = 1, modif.push_back(cv);
if (u == v)
{
earb[u] = false;
return;
}
if (siz[u] > siz[v])
swap(u, v);
parent[u] = v;
siz[v] += siz[u];
maxdeg[v] = max(maxdeg[v], maxdeg[u]);
if (earb[u] == false) earb[v] = false;
}
};
struct muchie
{
int u, v, c;
};
DSU dsu[obsize + 5];
//DSU dsu2[obsize + 5];
DSU aux;
int n, m;
vector<muchie> muc;
int cntbuc = 0;
void init(int N, int M, std::vector<int> u, std::vector<int> v, std::vector<int> w)
{
n = N, m = M;
for (int i = 0; i < m; i++)
{
muc.push_back({u[i], v[i], w[i]});
}
sort(muc.begin(), muc.end(), [](muchie a, muchie b)
{
return a.c < b.c;
});
aux.init(n);
dsu[0] = aux;
dsu[0].seteaza();
//dsu2[0] = dsu[0];
for (int i = 1; i <= m; i++)
{
aux.unite(muc[i - 1].u, muc[i - 1].v);
if (i % bucketsize == 0)
{
dsu[++cntbuc] = aux;
dsu[cntbuc].seteaza();
//dsu2[cntbuc] = dsu[cntbuc];
}
}
}
int getMinimumFuelCapacity(int uu, int vv)
{
int fbucket = 0;
//cout<<obsize<<endl;
for (int i = 1; i <= cntbuc; i++)
{
int u = dsu[i].cauta(uu);
int v = dsu[i].cauta(vv);
fbucket = i;
if (u == v && ((int)dsu[i].maxdeg[u] > 2 || !dsu[i].earb[u]))
{
fbucket--;
break;
}
}
//assert(fbucket == 0);
int fmuc = fbucket * bucketsize + 1;
int lim = min(m, fmuc + bucketsize);
for (int i = fmuc; i <= lim; i++)
{
dsu[fbucket].unite(muc[i - 1].u, muc[i - 1].v);
int u = dsu[fbucket].cauta(uu);
int v = dsu[fbucket].cauta(vv);
if (u == v && ((int)dsu[fbucket].maxdeg[u] > 2 || !dsu[fbucket].earb[u]))
{
//dsu[fbucket].reset();
//cout<<i<<" "<<u<<" "<<v<<" "<<(int)dsu[fbucket].maxdeg[u]<<" "<<dsu[fbucket].earb[u]<<" "<<fbucket<<'\n';
dsu[fbucket].reset();
return muc[i - 1].c;
}
}
dsu[fbucket].reset();
return -1;
}
