OI XXXI - wys (Alt1)

// https://szkopul.edu.pl/problemset/problem/vi23594m9-57bDiIC-M_ydYe/site/?key=statement

// author: pb0207

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

const int N = 1e6 + 1e3 + 7;

int n, m;

int fa[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int cov[N];

int a[N], dfn[N], tot;
namespace Rmq {
int st[15][N / 32];
int pre[N], p[N], w[N];
inline int min(int x, int y) {
    return dfn[x] < dfn[y] ? x : y;
}
inline void down(int& x, int y) {
    if (dfn[x] > dfn[y]) x = y;
}
inline int qry(int l, int r) {
    const int lg = std::__lg(r - l);
    return l >= r ? 0 : min(st[lg][l], st[lg][r - (1 << lg)]);
}
inline int rmq(int l, int r) {
    if (l >> 5 == r >> 5)
        return p[l + __builtin_ctz(w[r] >> l)];
    else
        return min(qry((l >> 5) + 1, r >> 5), min(a[l], pre[r]));
}
inline void build(int n) {
    ++(n |= 31);
    memcpy(p, a, n << 2);

    for (int i = 0; i < n; i += 32) {
        static int st[33];
        pre[i] = a[i];
        int *top = st + 1, s = 1;
        w[*top = i] = s;

        for (int j = i + 1; j < i + 32; ++j) {
            for (; top != st && dfn[a[j]] < dfn[a[*top]]; --top)
                s ^= 1 << *top;

            w[j] = s |= 1 << j;
            *++top = j;
            pre[j] = a[st[1]];
        }

        for (int j = i + 30; j >= i; --j)
            down(a[j], a[j + 1]);

        Rmq::st[0][i >> 5] = a[i];
    }

    for (int i = 1; i < 15; ++i)
        for (int j = 0; j + (1 << i) - 1 <= n / 32; ++j)
            st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
} // namespace Rmq
struct T {
    int to, nxt;
} way[N << 1];
int h[N], num;
inline void adde(int x, int y) {
    way[++num] = {y, h[x]}, h[x] = num;
    way[++num] = {x, h[y]}, h[y] = num;
}
int par[N];
inline void dfs(int x, int f) {
    par[x] = f;
    a[tot] = f;
    dfn[x] = ++tot;

    for (int i = h[x]; i; i = way[i].nxt)
        if (way[i].to != f) dfs(way[i].to, x);
}
inline int lca(int x, int y) {
    if (dfn[x] > dfn[y]) std::swap(x, y);

    return x == y ? x : Rmq::rmq(dfn[x], dfn[y] - 1);
}

void scov(int x, int f) {
    for (int i = h[x]; i; i = way[i].nxt)
        if (way[i].to != f) {
            scov(way[i].to, x);
            cov[x] += cov[way[i].to];
        }
}

void pcov(int x, int f) {
    for (int i = h[x]; i; i = way[i].nxt)
        if (way[i].to != f) {
            cov[way[i].to] += cov[x];
            pcov(way[i].to, x);
        }
}

void rd(int& x) {
    x = 0;
    char ch = getchar();
    int f = 1;

    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    x *= f;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    rd(n), rd(m);

    for (int i = 1; i <= n; i++)
        fa[i] = i;

    vector<pair<int, int>> ot;

    for (int i = 1; i <= m; i++) {
        int u, v;
        rd(u), rd(v);
        int fu = find(u), fv = find(v);

        if (fu == fv)
            ot.push_back({u, v});
        else
            fa[fu] = fv, adde(u, v);
    }

    dfs(1, 0);
    *dfn = 1e9;
    Rmq::build(n - 1);

    for (auto [x, y] : ot) {
        int p = lca(x, y);
        cov[x]++;
        cov[y]++;
        cov[p]--;
        cov[par[p]]--;
    }

    scov(1, 0);
    int sum = 0;

    for (int i = 1; i <= n; i++) {
        if (cov[i]) sum++;

        cov[i] = !cov[i];
    }

    cov[0] = 0;
    pcov(1, 0);
    int q;
    rd(q);
    cout << sum << "\n";

    while (q--) {
        int x, y;
        rd(x), rd(y);
        int p = lca(x, y);
        int ans = sum + cov[x] + cov[y] - cov[p] - cov[par[p]];
        cout << ans << "\n";
    }
}