#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define N 100000
#define INF 0x3f3f3f3f
int ds[N], ww1[N], ww2[N];
int find(int i) {
return ds[i] < 0 ? i : find(ds[i]);
}
void join(int i, int j, int w) {
i = find(i), j = find(j);
if (i == j)
ww2[i] = min(ww2[i], w);
else {
if (ds[i] > ds[j])
swap(i, j);
ds[i] += ds[j], ds[j] = i;
ww1[j] = w;
ww2[i] = min(ww2[i], ww2[j]);
}
}
void init(int n, int m, std::vector<int> ii, std::vector<int> jj, std::vector<int> ww) {
vector<int> hh(m);
for (int i = 0; i < m; i++)
hh[i] = i;
sort(hh.begin(), hh.end(), [&](int i, int j) {
return ww[i] < ww[j];
});
memset(ds, -1, n * sizeof *ds);
memset(ww1, 0x3f, n * sizeof *ww1);
memset(ww2, 0x3f, n * sizeof *ww2);
for (int h : hh)
join(ii[h], jj[h], ww[h]);
}
int getMinimumFuelCapacity(int i, int j) {
int w1 = -1;
while (i != j && (ds[i] >= 0 || ds[j] >= 0)) {
if (ww1[i] < ww1[j]) {
w1 = ww1[i];
i = ds[i];
} else {
w1 = ww1[j];
j = ds[j];
}
}
w1 = max(w1, ww2[i]);
return w1 == INF ? -1 : w1;
}
/*
int main() {
int _N, _M;
cin >> _N >> _M;
vector<int> _U(_M), _V(_M), _W(_M);
for (int i = 0; i < _M; i++)
cin >> _U[i] >> _V[i] >> _W[i];
init(_N, _M, _U, _V, _W);
int _Q;
cin >> _Q;
while (_Q--) {
int _u, _v;
cin >> _u >> _v;
cout << getMinimumFuelCapacity(_u, _v) << '\n';
}
}
*/
