#include <bits/stdc++.h>

template <bool union_by_size = true>
struct UF {
    int n, comp_cnt;
    std::vector<int> p;
    UF(int n_) : n(n_), comp_cnt(n), p(n, -1) {}
    int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    template <typename F>
    bool join(int x, int y, F&& f) {
        x = find(x), y = find(y);
        if (x == y) return false;
        comp_cnt--;
        if constexpr (union_by_size) {
            if (-p[x] > -p[y]) std::swap(x, y);
        }
        p[y] += p[x];
        f(x, y);
        p[x] = y;
        return true;
    }
    bool join(int x, int y) {
        return join(x, y, [](...){});
    }
    std::vector<int> group_sizes() {
        std::vector<int> sizes;
        for (int i = 0; i < n; i++) {
            if (p[i] < 0) {
                sizes.push_back(-p[i]);
            }
        }
        return sizes;
    }
    std::vector<std::vector<int>> groups() {
        std::vector<std::vector<int>> groups(n);
        for (int i = 0; i < n; i++) {
            groups[find(i)].push_back(i);
        }
        groups.erase(
                std::remove_if(begin(groups), end(groups), [](const std::vector<int>& v) { return v.empty(); }),
                end(groups));
        return groups;
    }
    int group_cnt() {
        return comp_cnt;
    }
    int size_of(int x) {
        return -p[find(x)];
    }
};
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int q;
    cin >> n >> q;
    vector<array<int, 2>> e(n + 1);
    vector<int> extra;
    UF uf(n);

    vector<vector<array<int, 2>>> g(n);
    for (int i = 0; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        e[i] = {u, v};
        if (uf.join(u, v)) {
            g[u].push_back({v, i});
            g[v].push_back({u, i});
        } else {
            extra.push_back(i);
        }
    }


    assert(size(extra) == 2);

    vector<int> pa(n), pai(n), dep(n);

    auto dfs = [&](auto& slf, int u) -> void {
        for (auto [v, i] : g[u]) {
            if (v == pa[u]) continue;
            pa[v] = u;
            pai[v] = i;
            dep[v] = dep[u] + 1;
            slf(slf, v);
        }
    };

    dfs(dfs, 0);

    auto add = [&](int idx) {
        auto [u, v] = e[idx];
        g[u].push_back({v, idx});
        g[v].push_back({u, idx});
    };

    add(extra[0]);
    add(extra[1]);

    vector<int> bad1(n + 1), bad2(n + 1);

    auto go = [&](vector<int>& st, int u, int v) {
        while (u != v) {
            if (dep[u] < dep[v]) swap(u, v);
            st[pai[u]] = 1;
            u = pa[u];
        }
    };

    bad1[extra[0]] = 1;
    go(bad1, e[extra[0]][0], e[extra[0]][1]);

    bad2[extra[1]] = 1;
    go(bad2, e[extra[1]][0], e[extra[1]][1]);
    
    vector<int> c(n, -1);
    int cur = 0;
    auto dfs2 = [&](auto& slf, int u, int p) -> int {
        c[u] = cur;
        int is_bad = 0, sum = 0;
        for (auto [v, i] : g[u]) {
            if (v == p) continue;
            if (bad1[i] || bad2[i]) {
                is_bad = 1;
            } else {
                sum += slf(slf, v, u);
            }
        }
        return sum + is_bad;
    };

    int mid = -1;
    for (int i = 0; i < n; i++) {
        if (c[i] == -1) {
            int cnt = dfs2(dfs2, i, i);
            assert(cnt == 1 || cnt == 2);
            if (cnt == 2) {
                mid = cur;
            }
            cur++;
        }
    }

    int com = 0, midp = -1;
    vector<int> t(n);
    for (int i = 0; i < n; i++) {
        com += bad1[i] && bad2[i];
    }

    set<int> endpoints;
    for (int i = 0; i < n; i++) {
        set<int> st;
        for (auto [v, idx] : g[i]) {
            int tt = bad1[idx] << 1 | bad2[idx];
            t[i] |= tt;
            if (tt) {
                st.insert(tt);
            }
        }
        if (size(st) == 3) endpoints.insert(i);
        // if (b1 && b2) {
        //     assert(midp == -1);
        //     midp = i;
        // }
    }

    if (com == 0) {
        for (int i = 0; i < n; i++) {
            if (t[i] == 3) {
                assert(midp == -1);
                midp = i;
            }
        }
    }

    auto is_mid = [&](int u) {
        return u == midp || c[u] == mid;
    };
    while (q--) {
        int u, v;
        cin >> u >> v;
        u--, v--;

        if (c[u] == c[v]) {
            cout << 1 << '\n';
        } else if (is_mid(u) || is_mid(v) || 
                (t[u] == t[v] && t[u] != 0 && com == 0)
                ) {
            cout << 2 << '\n';
        } else if ((t[u] == t[v] && t[u] != 0) || endpoints.count(u) || endpoints.count(v)) {
            cout << 3 << '\n';
        } else {
            cout << "4\n";
        }
    }

    return 0;
}