#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
int u, v, w;
};
struct info{
int t;
int vert;
int ed;
bool deg3;
};
int n, m;
vector<edge> e;
vector<vector<pair<int,int>>> parhist;
vector<vector<info>> inhist;
vector<int> deg;
int getpar(int x, int t){
auto &v = parhist[x];
int l = 0, r = (int)v.size() - 1;
int ret = v[0].second;
while(l <= r){
int mid = (l + r) / 2;
if(v[mid].first <= t){
ret = v[mid].second;
l = mid + 1;
}
else{
r = mid - 1;
}
}
return ret;
}
int fpar(int x, int t){
int p = getpar(x, t);
if(p == x) return x;
return fpar(p, t);
}
info getinfo(int x, int t){
auto &v = inhist[x];
int l = 0, r = (int)v.size() - 1;
info ret = v[0];
while(l <= r){
int mid = (l + r) / 2;
if(v[mid].t <= t){
ret = v[mid];
l = mid + 1;
}
else{
r = mid - 1;
}
}
return ret;
}
bool good(int root, int t){
info cur = getinfo(root, t);
if(cur.ed >= cur.vert) return true;
if(cur.deg3) return true;
return false;
}
bool ok(int t, int x, int y){
int rx = fpar(x, t);
int ry = fpar(y, t);
if(rx != ry) return false;
return good(rx, t);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
n = N;
m = M;
e.clear();
e.resize(m);
for(int i = 0; i < m; i++){
e[i] = {U[i], V[i], W[i]};
}
sort(e.begin(), e.end(), [](edge a, edge b){
return a.w < b.w;
});
parhist.assign(n, {});
inhist.assign(n, {});
deg.assign(n, 0);
for(int i = 0; i < n; i++){
parhist[i].push_back({0, i});
inhist[i].push_back({0, 1, 0, false});
}
for(int i = 1; i <= m; i++){
int u = e[i - 1].u;
int v = e[i - 1].v;
bool adddeg3 = false;
deg[u]++;
if(deg[u] == 3) adddeg3 = true;
deg[v]++;
if(deg[v] == 3) adddeg3 = true;
int ru = fpar(u, i - 1);
int rv = fpar(v, i - 1);
if(ru == rv){
info cur = getinfo(ru, i - 1);
cur.t = i;
cur.ed++;
cur.deg3 = cur.deg3 || adddeg3;
inhist[ru].push_back(cur);
}
else{
info a = getinfo(ru, i - 1);
info b = getinfo(rv, i - 1);
if(a.vert < b.vert){
swap(ru, rv);
swap(a, b);
}
parhist[rv].push_back({i, ru});
info cur;
cur.t = i;
cur.vert = a.vert + b.vert;
cur.ed = a.ed + b.ed + 1;
cur.deg3 = a.deg3 || b.deg3 || adddeg3;
inhist[ru].push_back(cur);
}
}
}
int getMinimumFuelCapacity(int X, int Y){
if(!ok(m, X, Y)) return -1;
int l = 1, r = m;
int ans = m;
while(l <= r){
int mid = (l + r) / 2;
if(ok(mid, X, Y)){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
return e[ans - 1].w;
}
