OI XXXI - wys (Alt)

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

#include <bits/stdc++.h>

struct Edge {
    int to;
    int id;
};

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<Edge>> adj(n + 1);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back({v, i});
        if (u != v) {
            adj[v].push_back({u, i});
        } else {
            adj[v].push_back({u, i});
        }
    }

    std::vector<int> depth(n + 1, 0);
    std::vector<std::vector<int>> up(n + 1, std::vector<int>(20, 0));

    std::vector<int> diff(n + 1, 0);
    std::vector<bool> in_cycle(n + 1, false);
    std::vector<bool> vis(n + 1, false);

    std::vector<int> post_order;
    post_order.reserve(n);

    struct State {
        int u;
        int p;
        int p_edge_id;
        int d;
        int edge_idx;
    };

    std::vector<State> st;
    st.push_back({1, 0, -1, 1, 0});
    vis[1] = true;

    while (!st.empty()) {
        auto& curr = st.back();
        int u = curr.u;

        if (curr.edge_idx == 0) {
            depth[u] = curr.d;
            up[u][0] = curr.p;
            for (int i = 1; i < 20; ++i) {
                up[u][i] = up[up[u][i - 1]][i - 1];
            }
        }

        bool moved_down = false;
        while (curr.edge_idx < adj[u].size()) {
            auto& edge = adj[u][curr.edge_idx++];
            if (edge.id == curr.p_edge_id) continue;

            int v = edge.to;
            if (!vis[v]) {
                vis[v] = true;
                st.push_back({v, u, edge.id, curr.d + 1, 0});
                moved_down = true;
                break;
            } else if (depth[v] <= depth[u]) {
                if (u == v) {
                    in_cycle[u] = true;
                } else {
                    diff[u]++;
                    diff[v]--;
                }
            }
        }

        if (!moved_down) {
            post_order.push_back(u);
            st.pop_back();
        }
    }

    std::vector<int> cov = diff;
    for (int u : post_order) {
        if (u != 1) {
            cov[up[u][0]] += cov[u];
        }
        if (cov[u] > 0 && u != 1) {
            in_cycle[u] = true;
            in_cycle[up[u][0]] = true;
        }
    }

    int initial_valid = 0;
    for (int i = 1; i <= n; ++i) {
        if (in_cycle[i]) {
            initial_valid++;
        }
    }
    std::cout << initial_valid << "\n";

    std::vector<int> pref(n + 1, 0);
    pref[0] = 0;
    for (int i = (int)post_order.size() - 1; i >= 0; --i) {
        int u = post_order[i];
        int cost = in_cycle[u] ? 0 : 1;
        pref[u] = pref[up[u][0]] + cost;
    }

    auto get_lca = [&](int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);
        int diff_depth = depth[u] - depth[v];

        for (int i = 0; i < 20; ++i) {
            if ((diff_depth >> i) & 1) {
                u = up[u][i];
            }
        }
        if (u == v) return u;

        for (int i = 19; i >= 0; --i) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    };

    int q;
    std::cin >> q;
    for (int i = 0; i < q; ++i) {
        int x, y;
        std::cin >> x >> y;
        int lca = get_lca(x, y);

        int path_cost = pref[x] + pref[y] - pref[lca] - pref[up[lca][0]];

        std::cout << initial_valid + path_cost << "\n";
    }

    return 0;
}