When dealing intersections of two segments connecting points on a circle, the following fact is commonly used (proof omitted):

• Suppose that the points on a circle is numbered clockwise (or counterclockwise). For pairwise distinct integers \(a,b,c, d\ (a<b, c<d)\), the segment connecting \(a\) and \(b\), and another between \(c\) and \(d\), share a point if and only if:
  • two segments \([a,b]\) and \([c,d]\) on a number line intersect, but not in an containment relationship (where one completely contains the other). Equivalently, \(a<c<b<d\) or \(c<a<d<b\) holds.

We will use this fact to simplify the observation steps. Consider the following problem:

• On a number line, you are given \(M\) segments \([A_i, B_i]\ (1\leq i\leq M)\) and \(Q\) segments \([C_j, D_j]\ (1\leq j\leq Q)\).
• For all \(i_1, i_2\ (1\leq i_1,i_2\leq M, i_1\neq i_2)\), two segments \([A_{i_1},B_{i_1}]\) and \([A_{i_2},B_{i_2}]\) are either disjoint or in an containment relationship (*).
• For each \(j=1,2,\dots,Q\), find the number of \(i\) such that \([A_i,B_i]\) and \([C_j,D_j]\) intersect but are not in an containment relationship. (It is guaranteed that \(A_i,B_i,C_j,D_j\) are pairwise distinct for any pairs \((i,j)\).)

For simplicity, we call the segment \([A_i,B_i]\) segment \(i\). If a segment \(i\) fully contains segment \(j\), we write \(i \supset j\).

Out of nowhere, consider a directed graph \(G\) representing the containment relationships of segments \(1,2,\dots,M\). Namely,

• \(G\) has exactly \((M+1)\) vertices \(0,1,\dots,M\).
• For all \(i,j\ (1\leq i,j\leq M, i\neq j)\), there is an edge from vertex \(i\) to vertex \(j\) if and only if there is no \(k\ (1\leq k\leq M, k\neq i, k\neq j)\) with \(i\supset k \supset j\).
• For all \(i\ (1\leq i\leq M)\), there is an edge from vertex \(0\) to vertex \(i\) if and only if there is no \(k\ (1\leq k\leq M, k\neq i)\) with \(k\supset i\).
• No other edges exist.

Since every pair of segments \(1,2,\dots,M\) are in a containment relationship or disjoint (*), \(G\) is a tree rooted at vertex \(0\) (proof omitted).

Now let us consider how to a query. For any integer \(x\), define the minimum contained segment \(m(x)\) as:

• among segments \(1,2,\dots,\), the index of the segment that contains \(x\) (i.e. \(A_i \leq x\leq B_i\)) with the minimum width \(B_i-A_i\), or \(0\) if no such segment exists.

Then the answer to the query against a segment \([C_j,D_j]\) coincides with the shortest distance between vertices \(m(C_j)\) and \(m(D_j)\) when \(G\) is regarded as an undirected tree.

Therefore, the problem can be solved by the following steps.

• Construct \(G\) and find \(m(x)\ (1\leq x\leq 2N)\), which can be done in \(O(H+M)\) time using a stack. (See the following code for more details.)
• Use the algorithm to find the Lowest Common Ancestor (LCA). The precalculation costs \(O(M\log M)\), and the per-query cost is \(O(\log M)\).

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> id(2 * n);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        id[a] = id[b] = i;
    }

    vector<int> min_cov(2 * n); // min_cov[i]: smallest interval that covers point i
    int K = 1;
    while ((1 << K) <= m) ++K;
    vector par(K, vector<int>(m + 1, -1));
    vector<int> dep(m + 1);
    stack<int> st;
    st.push(0);
    for (int i = 0; i < 2 * n; i++) {
        if (i & 1) {
            if (!id[i]) continue;
            if (st.top() == id[i]) {
                st.pop();
                par[0][id[i]] = st.top();
                dep[id[i]] = st.size();
            } else {
                st.push(id[i]);
            }
        } else {
            min_cov[i] = st.top();
        }
    }
    for (int k = 0; k < K - 1; k++) {
        for (int i = 0; i < m + 1; i++) {
            par[k + 1][i] = (par[k][i] == -1 ? -1 : par[k][par[k][i]]);
        }
    }

    auto lca = [&](int u, int v) -> int {
        if (dep[u] > dep[v]) swap(u, v);
        int d = dep[v] - dep[u];
        for (int k = 0; k < K; k++) {
            if (d >> k & 1) v = par[k][v];
        }
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (par[k][u] != par[k][v]) {
                u = par[k][u];
                v = par[k][v];
            }
        }
        return par[0][u];
    };

    int q;
    cin >> q;
    while (q--) {
        int c, d;
        cin >> c >> d;
        --c, --d;
        int u = min_cov[c];
        int v = min_cov[d];
        int l = lca(u, v);
        cout << dep[u] + dep[v] - dep[l] * 2 << '\n';
    }
}