#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<climits>
#include"swap.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n, m;
vector<pair<ll, pair<ll, ll>>> edges;
vector<vector<ll>> binlift;
vector<ll> depths;
vector<ll> swapp;
ll getp(ll x, vector<ll>& dsu) {
if (dsu[x] == x)return x;
return dsu[x] = getp(dsu[x], dsu);
}
void merge(ll a, ll b, ll x, vector<ll>& dsu) {
a = getp(a, dsu);
b = getp(b, dsu);
dsu[a] = x;
dsu[b] = x;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
for (ll i = 0; i < m; i++) {
edges.push_back({ W[i], {U[i], V[i]} });
}
sort(edges.begin(), edges.end());
vector<ll> dsu(n + m);
for (ll i = 0; i < n + m; i++)dsu[i] = i;
swapp.assign(n + m, LLONG_MAX / 2);
vector<vector<ll>>child(n + m);
vector<ll>deg(n, 0);
binlift.assign(n + m, vector<ll>(20, -1));
for (ll i = 0; i < m; i++) {
ll a = edges[i].ss.ff;
ll b = edges[i].ss.ss;
ll oa = a;
ll ob = b;
a = getp(a, dsu);
b = getp(b, dsu);
if (a != b) {
merge(a, b, i + n, dsu);
binlift[a][0] = i + n;
binlift[b][0] = i + n;
if (swapp[a] != LLONG_MAX / 2 || swapp[b] != LLONG_MAX / 2 || (deg[oa] >= 2 && deg[ob] >= 2)) {
swapp[i + n] = edges[i].ff;
}
child[i + n].push_back(a);
child[i + n].push_back(b);
}
else {
swapp[a] = min(swapp[a], edges[i].ff);
}
deg[oa]++;
deg[ob]++;
}
depths.assign(n + m, 0);
for (ll i = n + m - 1; i >= 0; i--) {
for (ll j = 0; j < child[i].size(); j++) {
depths[child[i][j]] = depths[i] + 1;
swapp[child[i][j]] = min(swapp[child[i][j]], swapp[i]);
}
}
for (ll i = n + m - 1; i >= 0; i--) {
ll j = 0;
while (binlift[i][j] != -1) {
binlift[i][j + 1] = binlift[binlift[i][j]][j];
j++;
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
if (depths[X] < depths[Y]) {
ll tmp = X;
X = Y;
Y = tmp;
}
while (depths[X] != depths[Y]) {
X = binlift[X][floor(log2(depths[X] - depths[Y]))];
}
while (X != Y) {
ll i = 19;
while (binlift[X][i] == binlift[Y][i] && i > 0)i--;
X = binlift[X][i];
Y = binlift[Y][i];
}
return swapp[X] == LLONG_MAX / 2 ? -1 : swapp[Y];
}
/*signed main() {
ll N, M;
cin >> N >> M;
vector<ll> U(M), V(M), W(M);
for (ll i = 0; i < M; i++)cin >> U[i] >> V[i] >> W[i];
init(N, M, U, V, W);
ll Q;
cin >> Q;
while (Q--) {
ll a, b;
cin >> a >> b;
cout << getMinimumFuelCapacity(a, b) << "\n";
}
}*/
