#include <bits/stdc++.h>
using namespace std;

const int MAXN = 32000 + 5;
const int INF = 1e9;

struct Edge {
    int to;
    int w; // 0 sau 1
};

vector<Edge> g[MAXN];
int N, M;

// pentru Dijkstra bidirecțional
int distF[MAXN], distB[MAXN];      // distanțe forward / backward
int seenF[MAXN], seenB[MAXN];      // timestamp pentru noduri "văzute" (au distanță setată)
int doneF[MAXN], doneB[MAXN];      // timestamp pentru noduri "finalizate" (extrase definitiv din coadă)

int curSeenF = 1, curSeenB = 1;
int curDoneF = 1, curDoneB = 1;

inline int getDistF(int u) {
    return (seenF[u] == curSeenF) ? distF[u] : INF;
}

inline int getDistB(int u) {
    return (seenB[u] == curSeenB) ? distB[u] : INF;
}

int bidirectional_dijkstra(int S, int T) {
    if (S == T) return 0;

    curSeenF++;
    curSeenB++;
    curDoneF++;
    curDoneB++;

    // cozi de priorități: (dist, nod)
    using PII = pair<int, int>;
    priority_queue<PII, vector<PII>, greater<PII>> pqF, pqB;

    // inițializare pentru sursă
    distF[S] = 0;
    seenF[S] = curSeenF;
    pqF.push({0, S});

    // inițializare pentru destinație (caut înapoi)
    distB[T] = 0;
    seenB[T] = curSeenB;
    pqB.push({0, T});

    int best = INF;

    while (!pqF.empty() || !pqB.empty()) {
        int minF = INF, minB = INF;

        // curățăm intrările vechi din coada forward
        while (!pqF.empty() && doneF[pqF.top().second] == curDoneF) {
            pqF.pop();
        }
        if (!pqF.empty()) {
            minF = pqF.top().first;
        }

        // curățăm intrările vechi din coada backward
        while (!pqB.empty() && doneB[pqB.top().second] == curDoneB) {
            pqB.pop();
        }
        if (!pqB.empty()) {
            minB = pqB.top().first;
        }

        // dacă ambele cozi s-au golit, gata
        if (minF == INF && minB == INF) break;

        // criteriu de oprire pentru Dijkstra bidirecțional
        if (best <= minF + minB) break;

        // alegem partea de extins: cea cu distanță curentă mai mică
        if (minF <= minB) {
            // extindem din S (forward)
            int d = pqF.top().first;
            int u = pqF.top().second;
            pqF.pop();

            if (doneF[u] == curDoneF) continue; // deja procesat
            if (d != getDistF(u)) continue;     // intrare învechită în coadă

            doneF[u] = curDoneF;

            // dacă u este deja procesat și din partea cealaltă,
            // putem actualiza soluția
            if (doneB[u] == curDoneB) {
                int cand = d + getDistB(u);
                if (cand < best) best = cand;
            }

            // relaxăm muchiile din u
            for (const auto &e : g[u]) {
                int v = e.to;
                int nd = d + e.w;
                int old = getDistF(v);
                if (nd < old) {
                    distF[v] = nd;
                    seenF[v] = curSeenF;
                    pqF.push({nd, v});
                }
            }
        } else {
            // extindem din T (backward)
            int d = pqB.top().first;
            int u = pqB.top().second;
            pqB.pop();

            if (doneB[u] == curDoneB) continue;
            if (d != getDistB(u)) continue;

            doneB[u] = curDoneB;

            if (doneF[u] == curDoneF) {
                int cand = d + getDistF(u);
                if (cand < best) best = cand;
            }

            // relaxăm muchiile din u
            for (const auto &e : g[u]) {
                int v = e.to;
                int nd = d + e.w;
                int old = getDistB(v);
                if (nd < old) {
                    distB[v] = nd;
                    seenB[v] = curSeenB;
                    pqB.push({nd, v});
                }
            }
        }
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("obiective.in", "r", stdin);
    freopen("obiective.out", "w", stdout);

    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        // muchia originală: u -> v
        // pe sens: cost 0; invers: cost 1
        g[u].push_back({v, 0});
        g[v].push_back({u, 1});
    }

    int T;
    cin >> T;
    while (T--) {
        int S, D;
        cin >> S >> D;
        int ans = bidirectional_dijkstra(S, D);
        cout << ans << '\n';
    }

    return 0;
}