#define taskname "SwappingCities"
#include <bits/stdc++.h>
using namespace std;
const int kMaxLog = 19;
const int kInf = 2e9;
struct DSUTree {
int x, timer;
vector<int> parent, deg, max_deg, edges, sz, in, out, k;
vector<vector<int>> g, jump;
DSUTree(int _x = 0) : x(_x), edges(0), max_deg(0), timer(0) {
parent.resize(x + 1);
deg.resize(x + 1);
max_deg.resize(x + 1);
edges.resize(x + 1);
sz.resize(x + 1, 0);
g.resize(x + 1);
for (int i = 1; i <= x; i++) {
sz[i] = 1;
parent[i] = i;
deg[i] = max_deg[i] = edges[i] = 0;
}
}
int FindSet(int u) {
return (parent[u] == u ? u : parent[u] = FindSet(parent[u]));
}
bool Unite(int u, int v) {
int cu = FindSet(u), cv = FindSet(v);
if (cu == cv) {
deg[u]++, deg[v]++;
max_deg[cu] = max({max_deg[cu], deg[u], deg[v]});
edges[cu]++;
return (max_deg[cu] >= 3 || edges[cu] >= sz[cu]);
}
parent[cu] = parent[cv] = ++x;
parent.push_back(x);
g.push_back({cu, cv});
sz.push_back(sz[cu] + sz[cv]);
edges.push_back(edges[cu] + edges[cv] + 1);
deg[u]++, deg[v]++;
max_deg.push_back(max({max_deg[cu], max_deg[cv], deg[u], deg[v]}));
return (max_deg[x] >= 3 || edges[x] >= sz[x]);
}
void DFS(int u) {
in[u] = ++timer;
for (int v : g[u]) {
jump[0][v] = u;
for (int i = 1; i < kMaxLog; i++) {
jump[i][v] = jump[i - 1][jump[i - 1][v]];
}
k[v] = min(k[v], k[u]);
DFS(v);
}
out[u] = timer;
}
bool Ancestor(int u, int v) {
return (in[u] <= in[v] && out[v] <= out[u]);
}
int LCA(int u, int v) {
if (Ancestor(u, v)) {
return u;
}
for (int i = kMaxLog - 1; i >= 0; i--) {
if (jump[i][u] >= 1 && !Ancestor(jump[i][u], v)) {
u = jump[i][u];
}
}
return jump[0][u];
}
};
DSUTree a;
vector<pair<int, int>> S;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
vector<int> p(M);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int x, int y) {
return W[x] < W[y];
});
a = DSUTree(N);
for (int i = 0; i < M; i++) {
U[p[i]]++, V[p[i]]++;
if (a.Unite(U[p[i]], V[p[i]])) {
S.push_back({a.FindSet(U[p[i]]), W[p[i]]});
}
}
a.in.resize(a.x + 1);
a.out.resize(a.x + 1);
a.jump.resize(kMaxLog, vector<int>(a.x + 1));
a.k.resize(a.x + 1, kInf);
for (auto i : S) {
a.k[i.first] = min(a.k[i.first], i.second);
}
a.DFS(a.x);
}
int getMinimumFuelCapacity(int X, int Y) {
X++, Y++;
int Z = a.LCA(X, Y);
return (a.k[Z] == kInf ? -1 : a.k[Z]);
}
//int main() {
// int N, M;
// vector<int> U, V, W;
// cin >> N >> M;
// for (int i = 1; i <= M; i++) {
// int u, v, w;
// cin >> u >> v >> w;
// U.push_back(u);
// V.push_back(v);
// W.push_back(w);
// }
// init(N, M, U, V, W);
// int Q;
// cin >> Q;
// while (Q--) {
// int X, Y;
// cin >> X >> Y;
// cout << getMinimumFuelCapacity(X, Y) << '\n';
// }
//}
