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

const int MAXN = 32000 + 5;
const int INF   = 1000000000;

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

int N, M;
vector<Edge> gf[MAXN]; // graf pentru căutarea din sursă (forward)
vector<Edge> gb[MAXN]; // graf invers pentru căutarea din destinaţie (backward)

// distanţe + timestamp-uri pentru a evita resetarea la fiecare întrebare
int distF[MAXN], distB[MAXN];
int seenF[MAXN], seenB[MAXN];
int doneF[MAXN], doneB[MAXN];

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;

    // "versiune" nouă pentru vectorii logici
    ++curSeenF; ++curSeenB;
    ++curDoneF; ++curDoneB;

    using PII = pair<int,int>;
    priority_queue<PII, vector<PII>, greater<PII>> pqF, pqB;

    distF[S] = 0;
    seenF[S] = curSeenF;
    pqF.push({0, S});

    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 coada forward
        while (!pqF.empty() && doneF[pqF.top().second] == curDoneF)
            pqF.pop();
        if (!pqF.empty())
            minF = pqF.top().first;

        // curăţăm coada backward
        while (!pqB.empty() && doneB[pqB.top().second] == curDoneB)
            pqB.pop();
        if (!pqB.empty())
            minB = pqB.top().first;

        if (minF == INF && minB == INF)
            break;

        // criteriu de oprire: doar dacă avem deja o soluţie finită
        if (best < INF && best <= minF + minB)
            break;

        if (minF <= minB) {
            // extindem din partea S (forward)
            auto [d, u] = pqF.top();
            pqF.pop();

            if (doneF[u] == curDoneF) continue;
            if (d != getDistF(u)) continue;

            doneF[u] = curDoneF;

            // dacă u a fost deja "terminat" şi de la T, avem candidat
            if (doneB[u] == curDoneB) {
                int cand = d + getDistB(u);
                if (cand < best) best = cand;
            }

            for (auto &e : gf[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 partea T (backward)
            auto [d, u] = pqB.top();
            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;
            }

            for (auto &e : gb[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

        // graf forward (S -> T)
        gf[u].push_back({v, 0}); // mergem pe sens -> cost 0
        gf[v].push_back({u, 1}); // invers -> întoarcem strada -> cost 1

        // graf backward (T -> S) = graful invers al celui de mai sus
        gb[v].push_back({u, 0}); // inversul lui u->v (0)
        gb[u].push_back({v, 1}); // inversul lui v->u (1)
    }

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

    return 0;
}