#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
const int logn = 20;
struct node{
int l = -1, r = -1, os = -1, be, ki, ert = 0;
bool jo = false;
};
struct el{
int u, v, c;
bool operator < (const el &e) const{
return c < e.c;
}
};
vector<node> g;
struct union_find{
vector<int> vos, vm, ind, fok;
vector<bool> jo;
void init(int n){
vm.assign(n, 1);
vos.assign(n, -1);
fok.assign(n, 0);
jo.assign(n, false);
ind.resize(n);
iota(ind.begin(), ind.end(), 0);
}
int os(int x){
return (vos[x] == -1 ? x : vos[x] = os(vos[x]));
}
bool unio(int a, int b, int ert){
//cout<<"union "<<a<<" "<<b<<"\n";
fok[a]++;
fok[b]++;
bool kesz = fok[a] > 2 || fok[b] > 2;
a = os(a);
b = os(b);
if(a == b){
jo[a] = true;
g.push_back({ind[a], -1, -1, 0, 0, ert, jo[a]});
ind[a] = (int)g.size()-1;
return false;
}
if(vm[a] < vm[b]) swap(a, b);
vos[b] = a;
vm[a] += (int)(vm[a] == vm[b]);
/*cout<<"new node: "<<ind[a]<<" "<<ind[b]<<" | "<<g.size()<<"\n";
cout<<"can solve: "<<jo[a]<<" "<<jo[b]<<" "<<kesz<<"\n";*/
if(jo[b] || kesz)
jo[a] = true;
g.push_back({ind[a], ind[b], -1, 0, 0, ert, jo[a]});
ind[a] = (int)g.size()-1;
return true;
}
};
int ido = 0;
void bejar(int akt, int os){
//cout<<akt<<" bejar\n";
if(akt == -1) return;
g[akt].os = os;
g[akt].be = ido++;
bejar(g[akt].l, akt);
bejar(g[akt].r, akt);
g[akt].ki = ido++;
}
vector<vector<int>> lca;
union_find csop;
int n;
int ose(int a, int b){
return g[a].be <= g[b].be && g[b].ki <= g[a].ki;
}
int get_lca(int a, int b){
if(ose(a, b))
return a;
for(int i = logn-1; i >= 0; i--)
if(!ose(lca[a][i], b))
a = lca[a][i];
return lca[a][0];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
vector<el> v(M);
for(int i = 0; i < M; i++)
v[i] = {U[i], V[i], W[i]};
sort(v.begin(), v.end());
g.assign(N, node());
csop.init(N);
for(el e : v)
csop.unio(e.u, e.v, e.c);
n = (int)g.size();
bejar(n-1, n-1);
/*cout<<n<<" g size\n";
for(int i = 0; i < n; i++)
cout<<g[i].os<<" ";
cout<<"\n";*/
lca.assign(n, vector<int>(logn, n-1));
for(int i = 0; i < n; i++)
lca[i][0] = g[i].os;
for(int j = 1; j < logn; j++)
for(int i = 0; i < n; i++)
lca[i][j] = lca[lca[i][j-1]][j-1];
}
int getMinimumFuelCapacity(int X, int Y) {
int p = get_lca(X, Y);
if(g[p].jo)
return g[p].ert;
for(int i = logn-1; i >= 0; i--)
if(!g[lca[p][i]].jo)
p = lca[p][i];
p = lca[p][0];
if(g[p].jo)
return g[p].ert;
return -1;
}
