Let \(G_n\) be a graph obtained by retaining the edges with weight at most \(n\) in the original graph.

Let \(D_j\) be the value of \(d(S_j,T_j)\) in the original graph. Also, let \(\mathcal P\) be a set of paths connecting vertices \(S_j\) and \(T_j\) on the original graph such that “the maximum weight of an edge in the path” equals \(D_j\).

• If \(W_{A_j} > D_j\): for all \(P \in \mathcal P\), edge \(A_j\) is not in \(P\), so increasing the weight of edge \(A_j\) does not change the maximum weight of an edge in the path \(P\); it remains \(D_j\). Thus, \(d(S_j,T_j)\) does not change as well.

• If \(W_{A_j} < D_j\): incrementing the weight of edge \(A_j\) results in \(W_{A_j} \leq D_j\), so for all \(P \in \mathcal P\), the maximum weight of an edge in the path \(P\) remains \(D_j\). Thus, \(d(S_j,T_j)\) is invariant.

• If \(W_{A_j} = D_j\): if there is a path \(P \in \mathcal P\) that does not contain edge \(A_j\), then the maximum weight of an edge in the path \(P\) remains \(D_j\), so \(d(S_j,T_j)\) is not affected. Conversely, if \(P\) contains edge \(A_j\) for all \(P \in \mathcal P\), then \(d(S_j,T_j)\) increases by one.

We can easily compare \(W_{A_j}\) and \(D_j\) by checking whether vertices \(S_j\) and \(T_j\) are connected in \(G_{W_{A_j}}\) and \(G_{W_{A_j}-1}\), thus using a Disjoint Set Union.

The issue left is to determine for each query\(W_{A_j} = D_j\) if there is a path \(P \in \mathcal P\) without edge \(A_j\). Here, there is no path \(P \in \mathcal P\) without edge edge \(A_j\) if and only if:

• on a graph obtained by truncating all edges with weights less than \(W_{A_j}\) in \(G_{W_{A_j}}\), edge \(A_j\) is a bridge; moreover, when we remove edge \(A_j\) to obtain two connected components, one of them contains vertex \(S_j\), and the other contains vertex \(T_j\).

Here, a “bridge” of a graph is a term refers to an edge such that removing it results in increasing the number of connected components. Given a graph with \(V\) vertices and \(E\) edges, an algorithm called LowLink enables us to enumerate the bridges in the graph in a total of \(O(V+E)\) time.

Thus, it is sufficient to determine the following two on “the graph obtained by truncating all edges with weights less than \(W_{A_j}\) in \(G_{W_{A_j}}\)”:

• Is edge \(A_j\) a bridge?
• If so, after removing edge \(A_j\) to obtain two connected component, does one of them contain vertex \(S_j\) and the other contain \(T_j\)?

The former can be checked fast with LowLink, and the latter with DFS-order. Thus, the problem has been solved. The complexity of the following implementation is \(O(N+M\alpha (N) + Q\log Q +(M+Q) \log M)\).

Bonus: although the complexity is worsen, instead of using LowLink we can use the similar algorithm as ABC295-G.

Sample code (C++):

#include<bits/stdc++.h>
#include "atcoder/dsu"

using namespace std;
using namespace atcoder;

class lowlink {
    int n;
    vector<vector<pair<int, int>>> G;
    vector<int> in, out, low;
    unordered_map<int, int> bridge;
    
    void dfs(int u, int p, int &k) {
        in[u] = low[u] = k++;
        for (auto [v, id]: G[u]) {
            if (in[v] < 0) {
                dfs(v, id, k);
                low[u] = min(low[u], low[v]);
                if (low[v] > in[u]) bridge[id] = v;
            } else if (id != p) {
                low[u] = min(low[u], in[v]);
            }
        }
        out[u] = k;
    }
    
    void init() {
        n = G.size();
        in.assign(n, -1);
        out.assign(n, -1);
        low.assign(n, -1);
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (in[i] < 0) dfs(i, -1, k);
        }
    }

public:
    lowlink(const vector<vector<pair<int, int>>> &G) : G(G) { init(); }
    
    bool query(int a, int s, int t) {
        assert(0 <= s and s < n);
        assert(0 <= t and t < n);
        assert(s != t);
        if (!bridge.count(a)) return false;
        int l = in[bridge[a]], r = out[bridge[a]];
        s = in[s], t = in[t];
        return (l <= s and s < r) xor (l <= t and t < r);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m), w(m);
    vector<vector<int>> weight(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        --u[i], --v[i], --w[i];
        weight[w[i]].push_back(i);
    }
    int q;
    cin >> q;
    vector<int> a(q), s(q), t(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> s[i] >> t[i];
        --a[i], --s[i], --t[i];
    }
    vector<int> ans(q, -1);
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return w[a[i]] < w[a[j]]; });
    
    // Process the queries where original d(s[j], t[j]) does not coincides with w[a[j]]
    dsu uf(n);
    int l = 0;
    for (int i = 0; i < m; i++) {
        int r = l;
        while (r < q and w[a[ord[r]]] == i) ++r;
        for (int j = l; j < r; j++) {
            if (uf.same(s[ord[j]], t[ord[j]])) ans[ord[j]] = 0;
        }
        for (int j: weight[i]) {
            uf.merge(u[j], v[j]);
        }
        for (int j = l; j < r; j++) {
            if (!uf.same(s[ord[j]], t[ord[j]])) ans[ord[j]] = 0;
        }
        l = r;
    }
    
    uf = dsu(n);
    int it = 0;
    for (int i = 0; i < m; i++) {
        vector<int> ls; // The set of representative elements of the currenct connected components that are connected to a weight-i edge
        for (int j: weight[i]) {
            ls.push_back(uf.leader(u[j]));
            ls.push_back(uf.leader(v[j]));
        }
        sort(ls.begin(), ls.end());
        ls.erase(unique(ls.begin(), ls.end()), ls.end());
        int sz = ls.size();
        vector<vector<pair<int, int>>> G(sz); // edge = (to, id)
        for (int j: weight[i]) {
            int nu = lower_bound(ls.begin(), ls.end(), uf.leader(u[j])) - ls.begin();
            int nv = lower_bound(ls.begin(), ls.end(), uf.leader(v[j])) - ls.begin();
            if(nu != nv) {
                G[nu].emplace_back(nv, j);
                G[nv].emplace_back(nu, j);
            }
        }
        lowlink lk(G);
        while (it < q and w[a[ord[it]]] == i) {
            int now = ord[it++];
            if (ans[now] != -1) continue;
            int ns = lower_bound(ls.begin(), ls.end(), uf.leader(s[now])) - ls.begin();
            int nt = lower_bound(ls.begin(), ls.end(), uf.leader(t[now])) - ls.begin();
            assert(ns != nt);
            assert(ns < sz and nt < sz);
            assert(ls[ns] == uf.leader(s[now]) and ls[nt] == uf.leader(t[now]));
            // Does ns-nt path always contain a[now] on G?
            ans[now] = lk.query(a[now], ns, nt);
        }
        for (int j: weight[i]) {
            uf.merge(u[j], v[j]);
        }
    }
    
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}