// ~~ Be name khoda ~~
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
const int maxn5 = 3e5 + 10;
const int lg = 21;
int parlca[lg][maxn5], par[maxn5], len[maxn5];
int h[maxn5], ans[maxn5], sar[maxn5], tah[maxn5];
bool masir[maxn5], allno = false;
vector <int> adj[maxn5];
vector <pair<int, int>> ed;
int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}
void dfs(int v){
if(!masir[v])
ans[v] = len[v];
for(int i = 1; i < lg && parlca[i - 1][v] != -1; i++)
parlca[i][v] = parlca[i - 1][parlca[i - 1][v]];
for(auto u : adj[v]){
ans[u] = ans[v];
parlca[0][u] = v;
h[u] = h[v] + 1;
dfs(u);
}
}
inline int lca(int a, int b){
if(h[a] < h[b])
swap(a, b);
int d = h[a] - h[b];
for(int i = 0; i < lg; i++) if((d >> i)&1)
a = parlca[i][a];
if(a == b)
return a;
for(int i = lg - 1; i >= 0; i--) if(parlca[i][a] != parlca[i][b]){
a = parlca[i][a];
b = parlca[i][b];
}
return parlca[0][a];
}
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
for(int i = 0; i < m; i++)
ed.pb({W[i], i});
sort(all(ed));
memset(par, -1, sizeof par);
int newnode = n;
memset(masir, true, sizeof masir);
for(int i = 0; i < n; i++)
sar[i] = tah[i] = i;
for(auto [w, id] : ed){
int u = get_par(U[id]), v = get_par(V[id]);
//cout << "ok " << u << ' ' << v << ' ' << U[id] << ' ' << V[id] << ' ' << w << endl;
if(u == v){
if(masir[u]){
masir[u] = false;
len[u] = w;
}
continue;
}
par[u] = newnode;
par[v] = newnode;
len[newnode] = w;
masir[newnode] = (masir[u] && masir[v]);
if(masir[newnode]){
bool re1 = U[id] == sar[u] || U[id] == tah[u];
bool re2 = V[id] == sar[v] || V[id] == tah[v];
masir[newnode] = re1 && re2;
if(masir[newnode]){
sar[newnode] = U[id] == sar[u] ? tah[u] : sar[u];
tah[newnode] = V[id] == sar[v] ? tah[v] : sar[v];
}
}
adj[newnode].pb(u);
adj[newnode].pb(v);
//cout << "ya merged " << newnode << ' ' << masir[newnode] << ' ' << sar[newnode] << ' ' << tah[newnode] << endl;
newnode++;
}
if(masir[newnode - 1]){
allno = true;
return;
}
memset(parlca, -1, sizeof parlca);
dfs(newnode - 1);
}
int getMinimumFuelCapacity(int x, int y){
if(allno)
return -1;
int c = lca(x, y);
return max({len[c], ans[x], ans[y]});
}
// hen?
