円環上の \(2\) 点を結ぶ線分同士の交差に関する問題では、以下の事実がよく用いられます。（証明は省略します。）

• 円環上に時計回り（あるいは反時計回り）に点が並んでいるとする。互いに相異なる整数 \(a,b,c, d\ (a<b, c<d)\) に対し、\(2\) 点 \(a,b\) を結ぶ線分と \(2\) 点 \(c,d\) を結ぶ線分が共有点を持つことは以下と同値である。
  • 数直線上の区間 \([a,b]\) と \([c,d]\) が共有点を持ち、かつ包含関係（片方がもう片方を完全に包含する関係）にない。すなわち、\(a<c<b<d\) または \(c<a<d<b\)。

本解説でも考察の簡略化のため上記の事実を用います。すなわち、以下のような問題を考えます。

• 数直線上の \(M\) 個の区間 \([A_i, B_i]\ (1\leq i\leq M)\) および \(Q\) 個の区間 \([C_j, D_j]\ (1\leq j\leq Q)\) が与えられる。
• 任意の \(i_1, i_2\ (1\leq i_1,i_2\leq M, i_1\neq i_2)\) について、\(2\) 区間 \([A_{i_1},B_{i_1}], [A_{i_2},B_{i_2}]\) は共有点を持たないか包含関係にあるかのいずれかである（＊）。
• \(j=1,2,\dots,Q\) それぞれについて、\([A_i,B_i]\) と \([C_j,D_j]\) が共有点を持ちかつ包含関係にないような \(i\) の個数を求めよ。（なお、任意の \(i,j\) の組について、\(A_i,B_i,C_j,D_j\) は互いに相異なることが保証される。）

以下、簡単のため区間 \([A_i,B_i]\) のことを区間 \(i\) と表記します。また、区間 \(i\) が区間 \(j\) を包含することを \(i \supset j\) と表記します。

唐突ですが、区間 \(1,2,\dots,M\) の包含関係を表す有向グラフ \(G\) を考えます。具体的な定義は以下の通りです：

• \(G\) は \(M+1\) 個の頂点 \(0,1,\dots,M\) からなる。
• 任意の \(i,j\ (1\leq i,j\leq M, i\neq j)\) について、\(i \supset j\) かつ、 \(i\supset k \supset j\) なる \(k\ (1\leq k\leq M, k\neq i, k\neq j)\) が存在しないとき、頂点 \(i\) から頂点 \(j\) に向かって辺が張られている。
• 任意の \(i\ (1\leq i\leq M)\) について、\(k\supset i\) なる \(k\ (1\leq k\leq M, k\neq i)\) が存在しないとき、頂点 \(0\) から頂点 \(i\) に向かって辺が張られている。
• 上記の辺以外に辺は存在しない。

このとき、区間 \(1,2,\dots,M\) は互いに共有点を持たないか包含関係にあるという条件（＊）から、\(G\) は頂点 \(0\) を根とする根付き木になります。（証明は省略します。）

下図はその具体例です。

さて、クエリの処理について考えましょう。任意の整数 \(x\) について、\(x\) の 最小包含区間 \(m(x)\) を以下のように定義します。

• 区間 \(1,2,\dots,M\) のうち、\(x\) を区間内に含む（すなわち \(A_i \leq x\leq B_i\)）ものであって、幅 \(B_i-A_i\) が最小であるようなものの番号。ただし、存在しなければ \(0\)。

このとき、区間 \([C_j,D_j]\) に対するクエリの答えは、\(G\) を無向木とみなしたときの頂点 \(m(C_j),m(D_j)\) 間の最短経路の長さに一致します。

よって、本問題は以下のようなアルゴリズムによって解くことができます。

• \(G\) を構築し、\(m(x)\ (1\leq x\leq 2N)\) の値を求める。これは stack を用いることで \(O(N+M)\) で実現できる。（詳細は下記の実装例を参照。）
• 最小共通祖先 (LCA) を求めるアルゴリズムを利用し、前計算 \(O(M\log M)\)、各クエリあたり \(O(\log M)\) でクエリの答えを求める。

実装例 (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';
    }
}