For each value g, the cities with indices $g,2g,3g,…$ will be connected together. There may exist pairs of cities whose gcd is greater than g, but since we process values of g from large to small, those gcd values have already been handled earlier. Based on this observation, we use parallel binary search to find the answer for each query.

Let day d correspond to value $g=M−d+1$

When processing day $d$, we merge all multiples of $g$:

for (int j = 2 * g; j <= n; j += g) {
    dsu.unite(g, j);
}

Time complexity: $O(n \log^2 m \cdot \alpha(n) + q \log m)$

Code:

struct DisjointSet {
    vector<int> par, num;
    int n;

    DisjointSet(int n) {
        this -> n = n;
    }

    void init() {
        par.assign(n + 5, 0);
        num.assign(n + 5, 0);
        iota(all(par), 0);
        fill(all(num), 1);
    }

    int findpar(int u) {
        return (par[u] == u ? u : par[u] = findpar(par[u]));
    }

    bool unite(int u, int v) {
        u = findpar(u);
        v = findpar(v);
        if (u == v) return false;

        if (num[u] < num[v]) swap(u,v);
        par[v] = u;
        num[u] += num[v];
        return true;
    }
};

struct infoQuery {
    int u, v;
};

constexpr int N = 1e5 + 1;
vector<int> canMid[N];
int n, q, m;

void solve() {
    cin >> n >> m >> q;
    vector<infoQuery> query(q + 1);

    For (i, 1, q) cin >> query[i].u >> query[i].v;

    vector<int> l(q + 1, 1), r(q + 1, m), ans(q + 1, m);

    For (i, 1, q) {
        if (query[i].u == query[i].v) {
            l[i] = m;
            r[i] = 1;
            ans[i] = 0;
        }
    }

    DisjointSet dsu(n);
    bool flag = true;
    while (flag) {
        flag = false;
        For (i, 1, q) {
            if (l[i] > r[i]) continue;
            flag = true;
            int mid = (l[i] + r[i]) >> 1;
            canMid[mid].pb(i);
        }

        if (!flag) break;

        dsu.init();
        For (i, 1, m) {
            int add = m - i + 1;
            for (int j = 2 * add; j <= n; j += add) {
                dsu.unite(add, j);
            }

            for (int id : canMid[i]) {
                auto &[u, v] = query[id];
                if (dsu.findpar(u) == dsu.findpar(v)) {
                    ans[id] = i;
                    r[id] = i - 1;
                } else {
                    l[id] = i + 1;
                }
            }

            vector<int>().swap(canMid[i]);
        }
    }

    For (i, 1, q) cout << ans[i] << endl;
}