#include "swap.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 200005;
using pii = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pii>;
using vvi = vector<vi>;
using vvpi = vector<vpi>;
#define pb push_back
struct edge{
int u, v, w;
int id = -1;
const bool operator< (edge other){return w < other.w;}
const bool operator> (edge other){return w > other.w;}
const bool operator<= (edge other){return w <= other.w;}
const bool operator>= (edge other){return w >= other.w;}
};
int n, m;
vpi cg[NMAX], cgmax[NMAX], cgd[NMAX];
int deg[NMAX], cnt1[NMAX], maxdeg[NMAX];
vi node[NMAX];
vector<edge> edges;
void merge(int t, int x, int y){
int a = cg[x].back().second, b = cg[y].back().second;
deg[x]++;
deg[y]++;
cgd[x].pb({t, deg[x]});
cgd[y].pb({t, deg[y]});
int md = max(deg[x], deg[y]);
if (a == b){
if (md > maxdeg[a]){
maxdeg[a] = md;
cgmax[a].pb({t, md});
}
return;
}
if (node[a].size() > node[b].size()){
swap(a, b);
}
while (!node[a].empty()){
int u = node[a].back();
node[b].push_back(u);
node[a].pop_back();
cg[u].push_back({t, b});
}
int upd = max(md, max(maxdeg[a], maxdeg[b]));
if (upd > maxdeg[b]){
maxdeg[b] = upd;
cgmax[b].pb({t, upd});
}
}
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++){
edges.pb({U[i], V[i], W[i]});
}
sort(edges.begin(), edges.end());
for (int i=0; i<n; i++){
node[i].pb(i);
cg[i].pb({0, i});
cgd[i].pb({0, 0});
cgmax[i].pb({0, 0});
}
int t=0;
for (edge e : edges){
merge(++t, e.u, e.v);
}
}
int getcomp(int u, int t){
if (cg[u].back().first <= t){
return cg[u].back().second;
}
pii sq = {t+1, 0};
pii last = *prev(lower_bound(cg[u].begin(), cg[u].end(), sq));
return last.second;
}
int getdeg(int u, int t){
pii sq = {t+1, 0};
pii last = *prev(lower_bound(cgd[u].begin(), cgd[u].end(), sq));
return last.second;
}
int getmd(int c, int t){
pii sq = {t+1, 0};
pii last = *prev(lower_bound(cgmax[c].begin(), cgmax[c].end(), sq));
return last.second;
}
bool check(int u, int v, int t){
int a = getcomp(u, t), b = getcomp(v, t);
if (a != b) {
return false;
}
if (getdeg(u, t) > 1 and getdeg(v, t) > 1){
return true;
}
return getmd(a, t) > 2;
}
int getMinimumFuelCapacity(int X, int Y) {
int l=1, r = m+1;
while (l < r){
int mid = (l+r)/2;
if (check(X, Y, mid)){
r = mid;
}
else{
l = mid+1;
}
}
if (l == m+1){
return -1;
}
return edges[l-1].w;
}
