#include "swap.h"
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;
const int MAXN = 1e5 + 20, MOD = 1e9 + 7, INF = 1e9;
struct Edge {
int u, v, w;
bool operator<(const Edge &other) {
return w < other.w;
}
};
struct DSU {
int n;
vi par, s, deg, mxDeg, timeValid;
vii root[MAXN];
vi g[MAXN];
void init(int n) {
this->n = n;
par.resize(n);
iota(all(par), 0);
s.assign(n, 1);
deg.assign(n, 0);
mxDeg.assign(n, 0);
timeValid.assign(n, INF);
for (int i = 0; i < n; i++)
root[i].eb(0, i);
}
int get(int x) {
return par[x];
}
void mark(int x, int newPar, int time) {
if (par[x] == newPar) return;
par[x] = newPar;
root[x].eb(time, newPar);
for (const auto &v : g[x]) mark(v, newPar, time);
}
void unite(int u, int v, int time) {
g[u].pb(v);
g[v].pb(u);
deg[u]++;
deg[v]++;
int x = get(u);
int y = get(v);
if (deg[u] >= 3) timeValid[x] = min(timeValid[x], time);
if (deg[v] >= 3) timeValid[y] = min(timeValid[y], time);
if (x == y) {
timeValid[x] = min(timeValid[x], time);
return;
}
if (s[x] > s[y]) {
swap(x, y);
swap(u, v);
}
s[y] += s[x];
timeValid[y] = min(timeValid[y], timeValid[x]);
mark(par[x], y, time);
}
bool query(int u, int v, int time) {
time++;
auto x = upper_bound(all(root[u]), ii(time, INF));
auto y = upper_bound(all(root[v]), ii(time, INF));
x--, y--;
ii rootU = *x;
ii rootV = *y;
if (rootU.second == rootV.second)
return timeValid[rootU.second] <= time;
return false;
}
};
DSU graph;
vector<Edge> edges;
int n, m;
void init(int N, int M, vi U, vi V, vi W) {
n = N;
m = M;
edges.resize(M);
for (int i = 0; i < M; i++) {
edges[i].u = U[i];
edges[i].v = V[i];
edges[i].w = W[i];
}
sort(all(edges));
graph.init(N);
for (int i = 0; i < M; i++)
graph.unite(edges[i].u, edges[i].v, i + 1);
}
int getMinimumFuelCapacity(int X, int Y) {
int lo = 0, hi = m - 1;
int ans = INF;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (graph.query(X, Y, mid)) {
ans = min(ans, edges[mid].w);
hi = mid - 1;
} else lo = mid + 1;
}
return ans < INF ? ans : -1;
}
//signed main() {
// FAST_IO;
//#ifdef arujbansal_local
// setIO("input.txt", "output.txt");
//#endif
//
// int a, b;
// cin >> a >> b;
// int u[b], v[b], wt[b];
//
// for (int i = 0; i < b; i++)
// cin >> u[i] >> v[i] >> wt[i];
//
// init(a, b, u, v, wt);
//
// int q;
// cin >> q;
// while (q--) {
// int x, y;
// cin >> x >> y;
// cout << getMinimumFuelCapacity(x, y) << "\n";
// }
//
//// for (const auto &[time, root] : graph.root[4])
//// cout << time << " " << root << "\n";
//}
