#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 forward (de la sursă la destinație)
vector<Edge> gb[MAXN]; // graf backward (invers)

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_01bfs(int S, int T) {
    if (S == T) return 0;

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

    deque<int> dqF, dqB;

    distF[S] = 0;
    seenF[S] = curSeenF;
    dqF.push_back(S);

    distB[T] = 0;
    seenB[T] = curSeenB;
    dqB.push_back(T);

    int best = INF;

    while (!dqF.empty() || !dqB.empty()) {
        int minF = INF, minB = INF;

        // curățăm din coada forward nodurile deja "finalizate"
        while (!dqF.empty() && doneF[dqF.front()] == curDoneF)
            dqF.pop_front();
        if (!dqF.empty())
            minF = getDistF(dqF.front());

        // curățăm din coada backward
        while (!dqB.empty() && doneB[dqB.front()] == curDoneB)
            dqB.pop_front();
        if (!dqB.empty())
            minB = getDistB(dqB.front());

        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 sursei (forward)
            int u = dqF.front(); dqF.pop_front();
            if (doneF[u] == curDoneF) continue;

            int d = getDistF(u);
            doneF[u] = curDoneF;

            // dacă u e deja finalizat și din partea cealaltă, 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;
                    if (e.w == 0) dqF.push_front(v);
                    else          dqF.push_back(v);
                }
            }
        } else {
            // extindem din partea destinației (backward)
            int u = dqB.front(); dqB.pop_front();
            if (doneB[u] == curDoneB) continue;

            int d = getDistB(u);
            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;
                    if (e.w == 0) dqB.push_front(v);
                    else          dqB.push_back(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
        gf[u].push_back({v, 0}); // pe sens -> cost 0
        gf[v].push_back({u, 1}); // invers -> cost 1 (trebuie întoarsă)

        // graf backward (inversul grafului forward)
        gb[v].push_back({u, 0});
        gb[u].push_back({v, 1});
    }

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

    return 0;
}