#include "bits/stdc++.h" using namespace std; #ifdef duc_debug #include "bits/debug.h" #else #define debug(...) #include "swap.h" #endif const int maxn = 3e5 + 5; const int LG = 19; int n, m; vector<int> g[maxn]; int eu[maxn], ev[maxn], ew[maxn]; int ord[maxn]; int deg[maxn]; bool ok[maxn]; int lab[maxn]; int val[maxn]; int num_nodes; int up[maxn][LG + 1], h[maxn], mn[maxn][LG + 1]; int find(int u) { return lab[u] < 0 ? u : lab[u] = find(lab[u]); } void join(int u, int v, int w) { int uu = u, vv = v; ++deg[uu], ++deg[vv]; u = find(u), v = find(v); ++num_nodes; val[num_nodes] = w; lab[num_nodes] = lab[u]; lab[u] = num_nodes; g[num_nodes].emplace_back(u); if (u != v) { lab[num_nodes] += lab[v]; lab[v] = num_nodes; g[num_nodes].emplace_back(v); } ok[num_nodes] = ok[u] | ok[v] | (u == v) | (deg[uu] > 2) | (deg[vv] > 2); } void dfs(int u) { for (auto v : g[u]) { up[v][0] = u; mn[v][0] = ok[u]; h[v] = h[u] + 1; for (int i = 1; i <= LG; ++i) { up[v][i] = up[up[v][i - 1]][i - 1]; mn[v][i] = max(mn[v][i - 1], mn[up[v][i - 1]][i - 1]); } dfs(v); } debug(u, up[u][0], val[u], ok[u]); } int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); for (int i = LG; i >= 0; --i) { if ((h[u] - h[v]) >> i & 1) u = up[u][i]; } if (u == v) return u; for (int i = LG; i >= 0; --i) { if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i]; } return up[v][0]; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N, m = M; for (int i = 0; i < m; ++i) { eu[i] = U[i], ev[i] = V[i], ew[i] = W[i]; ++eu[i], ++ev[i]; } iota(ord, ord + m, 0); sort(ord, ord + m, [](const int &x, const int &y) -> bool { return ew[x] < ew[y]; }); memset(lab, -1, sizeof(lab)); num_nodes = n; for (int i = 0; i < m; ++i) { join(eu[ord[i]], ev[ord[i]], ew[ord[i]]); } debug(num_nodes); dfs(num_nodes); } int getMinimumFuelCapacity(int u, int v) { ++u, ++v; int l = lca(u, v); if (ok[l]) return val[l]; for (int i = LG; i >= 0; --i) { if (up[l][i] and !mn[l][i]) l = up[l][i]; } l = up[l][0]; if (!l) return -1; return val[l]; } #ifdef duc_debug signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; vector<int> U, V, W; 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 u, v; cin >> u >> v; cout << getMinimumFuelCapacity(u, v) << '\n'; } return 0; } #endif