#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
const int N = 1e5 + 5;
int par[N][20], mx[N][20];
int tin[N], tout[N], t, is[N];
vector<ar<int, 2>> edges[N];
void dfs(int u, int p = -1){
for(int j=1;j<20;j++){
par[u][j] = par[par[u][j-1]][j-1];
mx[u][j] = max(mx[u][j-1], mx[par[u][j-1]][j-1]);
}
tin[u] = ++t;
for(auto x : edges[u]){
if(x[0] == p) continue;
par[x[0]][0] = u, mx[x[0]][0] = x[1];
dfs(x[0], u);
} tout[u] = t;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
vector<int> p(m); iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
return (w[i] < w[j]);
});
vector<int> par(n), sz(n, 1), d(n);
vector<vector<int>> sub(n);
for(int i=0;i<n;i++){
par[i] = i;
sub[i].push_back(i);
}
auto upd = [&](int a, int c){
for(auto x : sub[a]) is[x] = c;
sub[a].clear();
};
function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
auto merge = [&](int a, int b, int c){
d[a]++, d[b]++;
bool t = (d[a] >= 3 || d[b] >= 3);
a = f(a), b = f(b);
if(a == b){
upd(a, c);
return false;
}
if(sz[a] < sz[b]) swap(a, b);
par[b] = a, sz[a] += sz[b];
sub[a].insert(sub[a].end(), sub[b].begin(), sub[b].end());
if(is[a] && is[b]) return true;
if(!is[a] && !is[b]){
if(t) upd(a, c);
return true;
}
upd(a, c);
return true;
};
for(auto i : p){
if(merge(u[i], v[i], w[i])){
edges[u[i]].push_back({v[i], w[i]});
edges[v[i]].push_back({u[i], w[i]});
}
}
::par[0][0] = 1;
dfs(0, -1);
}
bool P(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int lca(int a, int b){
if(P(a, b)) return a;
if(P(b, a)) return b;
for(int j=19;~j;j--){
if(!P(par[a][j], b)) a = par[a][j];
} return par[a][0];
}
int getMinimumFuelCapacity(int a, int b) {
int mx = 0;
int p = lca(a, b);
//~ cout<<a<<" "<<b<<" "<<p<<"\n";
{
int x = a;
for(int j=19;~j;j--){
if(!P(par[x][j], p)){
mx = max(mx, ::mx[x][j]);
x = par[x][j];
}
} if(x != p) mx = max(mx, ::mx[x][0]);
}
{
int x = b;
for(int j=19;~j;j--){
if(!P(par[x][j], p)){
mx = max(mx, ::mx[x][j]);
x = par[x][j];
}
} if(x != p) mx = max(mx, ::mx[x][0]);
}
assert(mx);
if(!is[a]) return -1;
return max({mx, is[a], is[b]});
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/
