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

#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif

namespace {

constexpr int maxn = 50000 + 5;

int who[maxn];
bool din[maxn];
int covc = 1;
vector<int> cov[maxn];
vector<int> g[maxn];

bool instk[maxn], vis[maxn];
vector<int> stk;
void dfs(int u) {
    vis[u] = true;
    stk.push_back(u);
    instk[u] = true;
    for (int v : g[u]) {
        if (stk.size() >= 2 and v == stk[stk.size() - 2])
            continue;
        if (instk[v]) {
            for (auto it = stk.rbegin(); it != stk.rend(); ++it) {
                cov[*it].push_back(covc);
                if (*it == v) break;
            }
            covc += 1;
        } else if (not vis[v]) {
            dfs(v);
        }
    }
    instk[u] = false;
    stk.pop_back();
    vis[u] = true;
}

void dfs_din(int u) {
    din[u] = true;
    for (int v : g[u]) {
        if (cov[v].size() == 0 and not din[v])
            dfs_din(v);
    }
}

void dfs_who(int u, int f) {
    for (int v : g[u]) {
        if (v == f) continue;
        if (cov[v].size() == 0) {
            who[v] = who[u];
            dfs_who(v, u);
        }
    }
}

void solve1(int n, int q) {
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        for (int j : g[i])
            cnt += cov[j].size() == 2;
        if (cnt == 1) din[i] = true;

        if (din[i] and cov[i].size() == 2)
            dfs_din(i);
        if (cov[i].size() >= 1) {
            who[i] = i;
            dfs_who(i, i);
        }
    }

    while (q--) {
        int u, v;
        cin >> u >> v;
        if (who[u] == who[v]) {
            cout << 1 << '\n';
        } else {
            u = who[u], v = who[v];
            if ((din[u] and cov[u].size() == 2) or (din[v] and cov[v].size() == 2)) {
                cout << 3 << '\n';
            } else if (cov[u] == cov[v]) {
                cout << 3 << '\n';
            } else {
                cout << 4 << '\n';
            }
        }
    }
}

void solve2(int n, int q) {
    for (int i = 1; i <= n; ++i) {
        if (cov[i].size() >= 1) {
            who[i] = i;
            dfs_who(i, i);
        }
    }
    while (q--) {
        int u, v;
        cin >> u >> v;
        if (who[u] == who[v]) {
            cout << 1 << '\n';
        } else {
            u = who[u], v = who[v];
            if (cov[u].size() == 2 or cov[v].size() == 2) {
                cout << 2 << '\n';
            } else if (cov[u] == cov[v]) {
                cout << 2 << '\n';
            } else {
                cout << 4 << '\n';
            }
        }
    }
}

} // namespace

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n + 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
    
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (cov[i].size() == 2) cnt++;
        cout << i << ": [ ";
        for (auto x : cov[i]) cout << x << ' ';
        cout << "]\n";
    }
    cout << "cnt = " << cnt << '\n';
    if (cnt >= 2) solve1(n, q);
    else solve2(n, q);
    return 0;
}