#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
const int mxn = 2e5 + 10;
#define ff first
#define ss second
#define MP make_pair
typedef pair<int, int> pii;
vector<int> adj[mxn];
vector<pair<int, pii>> edges;
int cyc[mxn], anc[LOG][mxn];
int par[mxn], CNT, n, m;
int val[mxn], sus[mxn];
int parent(int u) { return par[u] < 0 ? u : par[u] = parent(par[u]); }
void unite(int u, int v, const int w, int &cnt) {
u = parent(u);
v = parent(v);
if(u == v) {
sus[u] = min(sus[u], w);
cyc[u] = 1;
return;
}
// par[cnt] += par[u];
// par[cnt] += par[v];
val[cnt] = w;
par[u] = par[v] = cnt;
cyc[cnt] = cyc[u] | cyc[v];
anc[0][u] = anc[0][v] = cnt;
adj[cnt].push_back(u);
adj[cnt].push_back(v);
cnt++;
}
int lvl[mxn];
void dfs(int u, int p = -1) {
// cout << u << ": " << val[u] << ", " << cyc[u] << endl;
for(int v : adj[u]) {
lvl[v] = lvl[u] + 1;
// cout << u << " -> " << v << endl;
dfs(v, u);
if(cyc[v]) assert(cyc[u]);
sus[u] = min(sus[u], sus[v]);
}
}
int LCA(int u, int v) {
if(lvl[u] < lvl[v]) swap(u, v);
int JUMP = lvl[u] - lvl[v];
for(int i = 0; i < LOG; i++)
if(JUMP & (1 << i)) {
u = anc[i][u];
}
assert(lvl[u] == lvl[v]);
if(u == v) return u;
for(int i = LOG - 1; i >= 0; i--)
if(anc[i][u] != anc[i][v]) {
u = anc[i][u];
v = anc[i][v];
}
return anc[0][u];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < M; i++) {
const int &u = U[i];
const int &v = V[i];
const int &w = W[i];
edges.emplace_back(w, MP(u, v));
}
n = N, m = M;
memset(par, -1, sizeof par);
for(int i = 0; i < LOG; i++)
memset(anc[i], -1, sizeof anc[i]);
memset(sus, 0x3f, sizeof sus);
int cnt = N;
sort(edges.begin(), edges.end());
for(const auto &p : edges) {
unite(p.ss.ff, p.ss.ss, p.ff, cnt);
}
assert(par[cnt - 1] == -1);
assert(cnt == 2 * n - 1);
for(int k = 1; k < LOG; k++)
for(int i = 0; i < cnt; i++) {
int j = anc[k - 1][i];
if(j > -1) {
anc[k][i] = anc[k - 1][j];
}
}
dfs(cnt - 1);
CNT = cnt;
if(cyc[cnt - 1] == 0)
assert(n - 1 == m);
}
int getMinimumFuelCapacity(int X, int Y) {
if(X == Y) return -1;
if(cyc[CNT - 1] == 0) return -1;
int A = LCA(X, Y);
if(cyc[A] == 1) return max(sus[A], val[A]);
for(int i = LOG - 1; i >= 0; i--) {
int B = anc[i][A];
if(B > -1 && cyc[B] == 0) {
A = B;
}
}
A = anc[0][A];
return max(val[A], sus[A]);
}
/*
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
*/
