#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
#define vi vector<int>
typedef long long ll;
typedef pair<int,int> P;
#define vp vector<P>
const int N=5e4+5;
int n,Q;
vector<P>egs[2]; int cnt;
vi tu0[N],tu[N];
int q[N],top,vis[N],ok[N];
void dfs(int now,int fa){
    // cout<<now<<' '<<fa<<endl;
    q[++top]=now; vis[now]=1; ok[now]=1;
    for(auto son:tu0[now]){
        if(son==fa)continue;
        if(vis[son]){
            if(!ok[son])continue;
            int tot=top;
            // cout<<now<<' '<<son<<"fz"<<endl;
            while(q[tot]!=son){
                // cout<<tot<<' '<<q[tot]<<"hhh"<<endl;
                egs[cnt].push_back({q[tot],q[tot-1]}),--tot;
            }
            ++cnt;
        }
        else {
            tu[now].push_back(son); tu[son].push_back(now); dfs(son,now);
        }
    }
    --top; ok[now]=0;
}
map<P,int>egmp[2];
void wk(int i){
    for(auto &[u,v]:egs[i]){
        if(u>v)swap(u,v);
        egmp[i][{u,v}]=1;
    }
}
vi vp2vi(vector<P>q){
    vi res(q.size()*2); int cnt=0;
    for(auto [u,v]:q)res[cnt++]=u,res[cnt++]=v;
    sort(res.begin(),res.end());
    res.resize(unique(res.begin(),res.end())-res.begin());
    return res;
}
int v1[N],v2[N],v3[N],fl,tp[N],rt[N],v0[N];

void dfs1(int now,int fa){
    if(fl)return;
    // cout<<now<<' '<<fa<<' '<<v2[now]<<endl;
    q[++top]=now;
    if(v2[now]){
        fl=1;
        while(1){
            int cur=q[top]; int tmp=v1[cur];
            // cout<<cur<<endl;
            v3[cur]=1; v2[cur]=v1[cur]=0;
            if(tmp)break;
        }
        return;
    }
    for(auto son:tu[now]){
        // cout<<now<<' '<<son<<"dfs"<<endl;
        if(fl)return;
        if(son==fa)continue;
        dfs1(son,now);
    }
    --top;
}
void dfs2(int now,int fa){
    // cout<<now<<' '<<fa<<"hh"<<endl;
    for(int son:tu[now]){
        if(son==fa || tp[son])continue;
        tp[son]=tp[now]; rt[son]=rt[now];
        dfs2(son,now);
    }
}
void slv1(vector<P>&com){
    vi p1=vp2vi(egs[0]),p2=vp2vi(egs[1]);
    vi p3=vp2vi(com);
    vi ct(n+1);
    for(auto [u,v]:com)++ct[u], ++ct[v];
    vi p0;
    rep(i,1,n){
        if(ct[i]&1)p0.push_back(i);
    }
    assert(p0.size()==2);
    for(auto p:p0){
        p1.erase(find(p1.begin(),p1.end(),p));
        p2.erase(find(p2.begin(),p2.end(),p));
        p3.erase(find(p3.begin(),p3.end(),p));
    }
    // for(auto v:p1)cout<<v<<' '; cout<<endl;
    // for(auto v:p2)cout<<v<<' '; cout<<endl;
    // for(auto v:p3)cout<<v<<' '; cout<<endl;
    // for(auto v:p0)cout<<v<<' '; cout<<endl;
    // exit(0);
    for(auto v:p1)tp[v]=1;
    for(auto v:p2)tp[v]=2;
    for(auto v:p3)tp[v]=3;
    for(auto v:p0)tp[v]=4;
    vi ok(n+1); rep(i,1,n)ok[i]=tp[i];
    rep(i,1,n){
        if(ok[i])rt[i]=i,dfs2(i,0);
    }
    while(Q--){
        int u,v;cin>>u>>v; int ans;
        if(max(tp[u],tp[v])==4)ans=3;
        else if(tp[u]==tp[v])ans=3;
        else ans=4;
        cout<<ans<<'\n';
    }
}
void slv2(){
    vi p1=vp2vi(egs[0]),p2=vp2vi(egs[1]);
    for(auto i:p1)v1[i]=1;
    for(auto i:p2)v2[i]=1;
    assert(!top);
    dfs1(p1[0],0);
    rep(i,1,n)if(v1[i])tp[i]=1;
    rep(i,1,n)if(v2[i])tp[i]=2;
    rep(i,1,n)if(v3[i])tp[i]=3;
    vi ok(n+1); rep(i,1,n)ok[i]=tp[i];
    rep(i,1,n){
        if(ok[i])rt[i]=i, dfs2(i,0);
    }
    // cout<<rt[1]<<' '<<rt[6]<<endl;
    while(Q--){
        int u,v;cin>>u>>v;
        int ans;
        if(tp[u]*tp[v]==9)ans=1;
        else if(max(tp[u],tp[v])==3)ans=2;
        else if(tp[u]!=tp[v])ans=4;
        else ans=1+(rt[u]!=rt[v]);
        cout<<ans<<'\n';
    }
}
int main(){
    IOS
    cin>>n>>Q;
    rep(i,1,n+1){
        int u,v;cin>>u>>v;
        tu0[u].push_back(v); tu0[v].push_back(u);
    }
    dfs(1,0); 
    assert(cnt==2);
    rep(i,0,1)wk(i);
    vector<P>com;
    for(auto p:egmp[0]){
        auto k=p.first;
        if(egmp[1].count(k))com.push_back(k);
    }
    if(com.size())slv1(com);
    else slv2();
}
/*
6 4
1 2
1 3
1 6
2 3
3 4
3 5
4 5

1 2
1 3
1 4
1 6


4 6
1 2
1 3
1 4
2 3
2 4

1 2
1 3
1 4
2 3
2 4
3 4

*/