#include "bits/stdc++.h"
using namespace std;
// #define int long long
const int N = 1e5 + 10;
// const int md = 1e9 + 7;
// const int INF = 1e18;
class DisjointSets {
private:
vector<int> p, sz, w1, w2;
public:
DisjointSets(int n) : p(n), sz(n), w1(n), w2(n) {
for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; w1[i] = w2[i] = 2e9;}
}
int get(int u) {
return p[u] = (u == p[u] ? u : get(p[u]));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v) {
return;
}
if (sz[v] > sz[u])
swap(u, v);
p[v] = u;
sz[u] += sz[v];
w1[u] = min(w1[u], w1[v]);
w2[u] = min(w2[u], w2[v]);
return;
}
int size(int u) {
return sz[get(u)];
}
void updatew1(int u, int val) {
u = get(u);
w1[u] = min(w1[u], val);
return;
}
void updatew2(int u, int val) {
u = get(u);
w2[u] = min(w2[u], val);
return;
}
int getw1(int u) {
return w1[get(u)];
}
int getw2(int u) {
return w2[get(u)];
}
};
DisjointSets dsu(N);
vector<vector<pair<int, int>>> g(N, vector<pair<int, int>> ());
vector<int> lvl(N);
vector<vector<int>> up(N, vector<int> (20, -1)), upmx(N, vector<int> (20));
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
vector<int> cnt(n + 1);
for (int i = 0; i < m; i++) {
if (dsu.get(U[i]) != dsu.get(V[i])) {
dsu.unite(U[i], V[i]);
cnt[U[i]]++, cnt[V[i]]++;
if (cnt[U[i]] == 3)
dsu.updatew1(U[i], W[i]);
if (cnt[V[i]] == 3)
dsu.updatew1(V[i], W[i]);
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
} else {
dsu.updatew2(U[i], W[i]);
}
}
function<void(int, int)> dfs = [&] (int u, int p) {
up[u][0] = p;
for (int msk = 1; msk < 20; msk++)
if (up[u][msk - 1] != -1) {
up[u][msk] = up[up[u][msk - 1]][msk - 1];
upmx[u][msk] = max(upmx[u][msk - 1], upmx[up[u][msk - 1]][msk - 1]);
}
for (auto v : g[u])
if (v.first != p) {
upmx[v.first][0] = v.second;
lvl[v.first] = lvl[u] + 1;
dfs(v.first, u);
}
}; dfs(0, -1);
}
int getMinimumFuelCapacity(int u, int v) {
int val = min(dsu.getw1(u), dsu.getw2(u));
if (lvl[u] > lvl[v]) {
int dst = lvl[u] - lvl[v];
for (int msk = 0; msk < 20; msk++)
if ((1 << msk) & dst) {
val = max(val, upmx[u][msk]);
u = up[u][msk];
}
}
if (lvl[v] > lvl[u]) {
int dst = lvl[v] - lvl[u];
for (int msk = 0; msk < 20; msk++)
if ((1 << msk) & dst) {
val = max(val, upmx[v][msk]);
v = up[v][msk];
}
}
if (u == v)
return (val == 2e9 ? -1 : val);
for (int msk = 19; msk >= 0; msk--)
if (up[u][msk] != up[v][msk]) {
val = max(val, upmx[u][msk]);
val = max(val, upmx[v][msk]);
u = up[u][msk];
v = up[v][msk];
}
val = max(val, upmx[u][0]);
val = max(val, upmx[v][0]);
return (val == 2e9 ? -1 : val);
}
// int32_t main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr); cout.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// }
// return 0;
// }
