#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tuple<int, int, int> ti;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#define debugArr(...)
#endif
const int MOD = 1000000007;
const char nl = '\n';
const int N = 1e5;
const int inf = 2e9;
int par[N], comp_size[N], merged[N], time_valid[N], deg[N];
int find(int a) {
while (par[a] != a) a = par[a];
return a;
}
void join(int a, int b, int time) {
deg[a]++;
deg[b]++;
bool athree = deg[a] >= 3;
bool bthree = deg[b] >= 3;
a = find(a);
b = find(b);
if (athree) time_valid[a] = min(time_valid[a], time);
if (bthree) time_valid[b] = min(time_valid[b], time);
if (a == b) {
time_valid[a] = min(time_valid[a], time);
return;
}
if (comp_size[a] < comp_size[b]) swap(a, b);
// cout << b << " into " << a << nl;
time_valid[a] = min(time_valid[a], max(time, time_valid[b]));
par[b] = a;
comp_size[a] += comp_size[b];
merged[b] = time;
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < n; i++) {
comp_size[i] = 1;
par[i] = i;
time_valid[i] = inf;
merged[i] = 0;
}
vector<int> edges(m);
iota(edges.begin(), edges.end(), 0);
sort(edges.begin(), edges.end(), [&] (auto &a, auto &b) {
return W[a] < W[b];
});
for (int &i: edges) {
int u = U[i];
int v = V[i];
int w = W[i];
join(u, v, w);
}
}
int getMinimumFuelCapacity(int X, int Y) {
// ans is max(min(valid on path to root), max(merge on path to lca))
int merge_time = 0;
int valid_time = inf;
if (find(X) != find(Y)) return -1;
int x = X;
int y = Y;
while(x != y) {
// debug(x, y);
if (comp_size[x] > comp_size[y]) swap(x, y);
valid_time = min(valid_time, max(merge_time, time_valid[x]));
merge_time = max(merge_time, merged[x]);
x = par[x];
}
// debug(x, time_valid[4]);
// debug(merge_time, valid_time);
int ans = merge_time;
while(merged[x] != 0) {
valid_time = min(valid_time, max(merge_time, time_valid[x]));
merge_time = max(merge_time, merged[x]);
x = par[x];
}
valid_time = min(valid_time, max(merge_time, time_valid[x]));
ans = max(ans, valid_time);
if (ans == inf) return -1;
return ans;
}
// struct UF {
// vi id, valid, degg;
// UF (int n): id(n), valid(n), degg(n) {
// iota(all(id), 0);
// }
// int find(int a) {
// if (id[a] == a) return a;
// return id[a] = find(id[a]);
// }
// void join(int a, int b) {
// degg[a]++; degg[b]++;
// bool v = (degg[a] >= 3 || degg[b] >= 3);
// a = find(a);
// b = find(b);
// if (a == b) {
// valid[a] = 1;
// return;
// }
// id[b] = a;
// valid[a] |= v | valid[b];
// }
// };
// int main() {
// int n, m, q; cin >> n >> m >> q;
// vector<ti> edges;
// vi A, B, W;
// rep(i, 0, m) {
// int a, b, c; cin >> a >> b >> c;
// A.pb(a);
// B.pb(b);
// W.pb(c);
// edges.pb({c, a, b});
// }
// init(n, m, A, B, W);
// sort(all(edges));
// while(q--) {
// int a, b; cin >> a >> b;
// UF uf(n);
// int ans = -1;
// for (auto &[c, u, v]: edges) {
// // debug(c, u, v);
// uf.join(u, v);
// if (uf.find(a) == uf.find(b) && uf.valid[uf.find(a)]) {
// ans = c;
// break;
// }
// }
// cout << ans << " " << getMinimumFuelCapacity(a, b) << nl;
// assert(ans == getMinimumFuelCapacity(a, b));
// }
// }
