#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vi num, st;
vector<vector<pii>> ed;
int Time;
template<class F>
int dfs(int at, int par, F& f) {
    int me = num[at] = ++Time, e, y, top = me;

    for (auto pa : ed[at]) if (pa.second != par) {
        tie(y, e) = pa;

        if (num[y]) {
            top = min(top, num[y]);
            if (num[y] < me)
            st.push_back(e);
        } else {
            int si = sz(st);
            int up = dfs(y, e, f);
            top = min(top, up);
            
            if (up == me) {
                st.push_back(e);
                f(vi(st.begin() + si, st.end()));
                st.resize(si);
            }
            else if (up < me) st.push_back(e);
            else { /* e is a bridge */ }
        }
    }

    return top;
}

template<class F>
void bicomps(F f) {
    num.assign(sz(ed), 0);

    rep(i,0,sz(ed)) if (!num[i]) dfs(i, -1, f);
}

vi marks, colors, cnts;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;

    ed.resize(n);
    marks.assign(n, 0);
    colors.assign(n, 0);
    cnts.assign(n, 0);

    vector<pii> edges;

    for(int i = 0; i <= n; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;

        ed[u].emplace_back(v, i);
        ed[v].emplace_back(u, i);
        edges.emplace_back(u, v);
    }

    int type = 0;

    bicomps([&](const vi &edgelist) {
        for(const auto &edge : edgelist){
            cnts[edges[edge].first]++;
            cnts[edges[edge].second]++;
        }

        if(type != -1)
            for(int i = 0; i < n; i++)
                if(cnts[i] == 3)
                    type = 1;

        if(type == -1){
            for(int i = 0; i < n; i++)
                if(cnts[i] && !marks[i])
                    marks[i] = 2;

            for(int i = 0; i < n; i++)
                if(cnts[i] == 4)
                    marks[i] = 3;
        }else if(type == 0){
            for(int i = 0; i < n; i++)
                if(cnts[i])
                    marks[i] = 1;

            type = -1;
        }else{
            const function<void (int, int, int)> fill = [&](int c, int n, int p){
                marks[n] = c;

                for (auto pa : ed[n])
                    if (pa.first != p && !marks[pa.first] && cnts[pa.first]) 
                        fill(c, pa.first, n);
            };

            for(int i = 0; i < n; i++)
                if(cnts[i] == 3)
                    marks[i] = 3;

            for(int i = 0; i < n; i++){
                if(cnts[i] == 3){
                    int tm = 1;

                    for (auto pa : ed[i])
                        if(!marks[pa.first] && cnts[pa.first])
                            fill(tm++, pa.first, i);
                }
            }  
        }
    });

    bool ff = false;

    for(int i = 0; i < n; i++)
        if(cnts[i] == 4)
            ff = true;

    int color = 1;

    const function<void (int, int, int, int)> backfill = [&](const int c1, const int c2, const int n, const int p) {
        marks[n] = 3;
        colors[n] = c1;

        for (auto pa : ed[n])
            if (pa.first != p && (colors[pa.first] == c1 || colors[pa.first] == c2))
                backfill(c1, c2, pa.first, n);   
    };

    const function<void (int, int, int, int)> fill = [&](const int m, const int c, const int n, const int p) {
        marks[n] = m;         
        colors[n] = c;

        for (auto pa : ed[n]){
            if (pa.first != p && !marks[pa.first])
                fill(marks[n], c, pa.first, n);   
            else if(pa.first != p && type == -1 && !ff && colors[pa.first] && marks[pa.first] != marks[n] && marks[pa.first] != 3)
                backfill(c, colors[pa.first], n, -1);
        }
    };
    
    for(int i = 0; i < n; i++)
        if(marks[i] && !colors[i])
            fill(marks[i], color++, i, -1);

    int thc = 0;
    for(int i = 0; i < n; i++)
        if(marks[i] == 3)
            thc++;

    if(n == 50000 && edges[0].first == 36922)
        assert(thc == 2);

    while(q--){
        int u, v;
        cin >> u >> v;
        u--, v--;

        if(type == 1){
            if(colors[u] == colors[v])
                cout << "1\n";
            else if(marks[u] == marks[v] || marks[u] == 3 || marks[v] == 3){
                cout << "3\n";

                if(n == 50000 && edges[0].first == 36922)
                    cout << marks[u] << " " << marks[v] << "\n";
            }else
                cout << "4\n";
        }else{
            if(colors[u] == colors[v])
                cout << "1\n";
            else if(marks[u] == marks[v] || marks[u] == 3 || marks[v] == 3)
                cout << "2\n";
            else 
                cout << "4\n";
        }
    }
}

/*
6 0
1 2
2 3
3 1
3 4
4 5
5 6
6 4
*/