#ifndef mikevui
// #include "task.h"
#endif // mikevui
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
struct edge{
int u, v, w;
edge(int _u, int _v, int _w) {
u = _u;
v = _v;
w = _w;
}
};
const int maxn = 3e5+5, lg = 19;
int n, m, trsz;
vector<edge> edges;
bool can[maxn];
int ans[maxn];
vector<int> adj[maxn];
int par[maxn][lg+1], h[maxn];
bool hadcan[maxn][lg+1];
namespace dsu{
vector<int> dsu, deg, sumdeg;
void init() {
trsz = n;
memset(can, 0, sizeof(can));
dsu.assign(trsz+1, 0);
deg.assign(trsz+1, 0);
sumdeg.assign(trsz+1, 1);
for (int i = 1; i <= n; i++) {
dsu[i] = i;
}
}
int f(int u) {
if (u == dsu[u]) return u;
return dsu[u] = f(dsu[u]);
}
void addedge(int u, int v) {
int ru = f(u), rv = f(v);
++trsz;
dsu.pb(trsz);
dsu[ru] = dsu[rv] = trsz;
adj[trsz].pb(ru);
if (ru != rv) adj[trsz].pb(rv);
++deg[u];
++deg[v];
//check cycle
sumdeg.pb(sumdeg[ru]);
if (ru != rv) sumdeg[trsz] += sumdeg[rv];
if (deg[u] == 2)--sumdeg[trsz];
if (deg[v] == 2)--sumdeg[trsz];
// cout << u << ' ' << v << ' ' << trsz << "\n" << deg[u] << ' ' << deg[v] << ' ' << sumdeg[ru] << ' ' << sumdeg[rv] << ' ' << sumdeg[trsz] << "\n";
can[trsz] = (max(deg[u], deg[v])>2 || sumdeg[trsz] == 0);
}
}
void dfs(int u) {
//setup binlift
for (int j = 1; j <= lg; j++) {
par[u][j] = par[par[u][j-1]][j-1];
hadcan[u][j] = hadcan[u][j-1]|hadcan[par[u][j-1]][j-1];
}
//dfs
for (int v : adj[u]) {
par[v][0] = u;
hadcan[v][0] = can[u];
h[v] = h[u]+1;
dfs(v);
}
}
int lca(int u, int v) {
if (h[u] < h[v]) swap(u, v);
if (h[u] > h[v]) {
int k = h[u]-h[v];
for (int j = lg; j >= 0; j--) {
if (BITj(k, j)) {
u = par[u][j];
}
}
}
if (u == v) return u;
for (int j = lg; j >= 0; j--) {
while (h[u] > MASK(j) && par[u][j] != par[v][j]) {
u = par[u][j];
v = par[v][j];
}
}
return par[u][0];
}
int findnearest(int u){
for (int j = lg; j >= 0; j--) {
while (h[u] > MASK(j) && !hadcan[u][j]) {
u = par[u][j];
}
}
return par[u][0];
}
void init(int N, int M, int U[], int V[], int W[]) {
//transform to normal use
n = N;
m = M;
for (int i = 0; i < m; i++) {
int u = U[i]+1, v = V[i]+1, w = W[i];
edges.pb(edge(u, v, w));
}
//build dsu tree
sort(edges.begin(), edges.end(), [&](edge a, edge b){return a.w<b.w;});
dsu::init();
for (int i= 0; i < m; i++) {
dsu::addedge(edges[i].u, edges[i].v);
ans[trsz] = edges[i].w;
}
//build binlift
memset(par, 0, sizeof(par));
memset(hadcan, 0, sizeof(hadcan));
memset(h, 0, sizeof(h));
for (int i = 1; i <= trsz; i++) {
if (!h[i]) {
h[i] = 1;
dfs(i);
}
}
// for (int i = 1; i <= trsz; i++) {
// cout << i << ' ' << h[i] << ' ' << can[i] << ' ' << ans[i] << "\n";
// }
}
int getMinimumFuelCapacity(int X, int Y) {
int x = X+1, y = Y+1;
//lca
int l = lca(x, y);
//check if lca can
if (can[l]) {
return ans[l];
}
//if not -> find nearest can
l = findnearest(l);
//case cannot
if (!can[l]) return -1;
return ans[l];
}
#ifdef mikevui
int U[maxn], V[maxn], W[maxn];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
int N, M;
cin >> N >> 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 X, Y;
cin >> X >> Y;
cout << getMinimumFuelCapacity(X,Y) << "\n";
}
}
#endif // mikevui
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
1
1 2
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
*/
Compilation message
/usr/bin/ld: /tmp/ccG1ky2x.o: in function `main':
grader.cpp:(.text.startup+0x1c3): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
