#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
#define db double
#define ll long long

const int maxn=5e4+10;
int n,q;
vector<int>v[maxn];
int f[maxn];
int getf(int x){
    return x==f[x]?x:(f[x]=getf(f[x]));
}
int a1,b1;
int a2,b2;
int fa[maxn];
int de[maxn];
void dfs1(int x){
    de[x]=de[fa[x]]+1;
    for(int y:v[x]){
        if(y==fa[x])continue;
        fa[y]=x;
        dfs1(y);
    }
}
map<pair<int,int>,int>ty;
void insty(int x,int y,int t){
    // cout<<x<<" "<<y<<" "<<t<<" insty\n";
    ty[mpr(min(x,y),max(x,y))]|=t;
    
}
int getty(int x,int y){
    return ty[mpr(min(x,y),max(x,y))];
}
void jumpandtag(int x,int y,int t){
    // cout<<x<<" "<<y<<" "<<t<<"\n";
    if(de[x]<de[y])swap(x,y);
    while(de[x]>de[y]){
        insty(x,fa[x],t);
        x=fa[x];
    }
    while(x!=y){
        insty(x,fa[x],t);
        insty(y,fa[y],t);
        x=fa[x],y=fa[y];
    }
    return;
}
int nodety[maxn];
int rt[maxn];
int dfsfind2(int x,int fa){
    for(int y:v[x]){
        if(y==fa)continue;
        int tmp=getty(x,y);
        if(tmp==1)continue;
        if(tmp==2)return 1;
        if(dfsfind2(y,x))return 1;
    }
    return 0;
}
void dfstag0(int x,int r){
    nodety[x]=0;
    rt[x]=r;
    for(int y:v[x]){
        if(nodety[y]!=-1)continue;
        if(getty(x,y)==0){
            dfstag0(y,r);
        }
    }
}
void dfstag1(int x,int r){
    nodety[x]=1;
    rt[x]=r;
    for(int y:v[x]){
        if(nodety[y]!=-1)continue;
        if(getty(x,y)==0){
            dfstag1(y,r);
        }
    }
}
void dfstag2(int x,int r){
    nodety[x]=2;
    rt[x]=r;
    for(int y:v[x]){
        if(nodety[y]!=-1)continue;
        if(getty(x,y)==0){
            dfstag2(y,r);
        }
    }
}
void solve0(){
    // cerr<<"solve ty0\n";
    memset(nodety,-1,sizeof nodety);
    for(int i=1;i<=n;i++){
        int ok=0;
        for(int j:v[i]){
            if(getty(i,j)==1)ok=1;
            // cout<<i<<" "<<j<<" "<<getty(i,j)<<"\n";
        }
        if(ok){
            int u=dfsfind2(i,0);
            if(u==1){
                // cout<<i<<" 0\n";
                dfstag0(i,i);
            }
            else{
                // cout<<i<<" 1\n";

                dfstag1(i,i);
            }
        }
    }
    for(int i=1;i<=n;i++){
        int ok=0;
        for(int j:v[i]){
            if(getty(i,j)==2)ok=1;
        }
        if(ok){
            if(nodety[i]==-1){
                dfstag2(i,i);
            }
        }
    }
    // for(int i=1;i<=n;i++){
    //     cout<<nodety[i]<<" \n"[i==n];
    // }
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        int aa=a,bb=b;
        a=nodety[a];
        b=nodety[b];
        if(a>b)swap(a,b);
        if(a==0&&b==0)cout<<"1\n";
        else if(a==0)cout<<"2\n";
        else if(a==b){
            if(rt[aa]==rt[bb])cout<<"1\n";
            else cout<<"2\n";
        }
        else cout<<"4\n";
    }
    return;
}
void dfstag(int x,int t,int r){
    nodety[x]=t;
    rt[x]=r;
    for(int y:v[x]){
        if(nodety[y]!=-1)continue;
        if(getty(x,y)==0){
            dfstag(y,t,r);
        }
    }
}
void solve1(){
    // cerr<<"solve ty1\n";
    int ty=3;
    for(int i=1;i<=n;i++){
        int h1=0,h2=0,h3=0;
        for(int j:v[i]){
            int tmp=getty(i,j);
            if(tmp==1){
                h1=1;
            }
            if(tmp==2)h2=1;
            if(tmp==3)h3=1;
        }
        if(h1+h2+h3==3){
            ++ty;
            dfstag(i,ty,i);
        }
        else{
            if(h1){
                dfstag(i,1,i);
            }
            else if(h2){
                dfstag(i,2,i);
            }
            else if(h3){
                dfstag(i,3,i);
            }
        }
    }
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        int aa=a,bb=b;
        a=nodety[a];
        b=nodety[b];
        if(a>b)swap(a,b);
        if(a<=3&&b<=3){
            if(a==b){
                if(rt[aa]==rt[bb])cout<<"1\n";
                else cout<<"3\n";
            }
            else{
                cout<<"4\n";
            }
        }
        else{
            if(a<=3){
                cout<<"3\n";
            }
            else{
                if(a==b){
                    if(rt[aa]==rt[bb]){
                        cout<<"1\n";
                    }
                    else assert(0);
                }
                else{
                    cout<<"3\n";
                }
            }
        }
    }
}
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=n+1;i++){
        int a,b;
        cin>>a>>b;
        if(getf(a)!=getf(b)){
            v[a].pb(b);
            v[b].pb(a);
            f[getf(a)]=getf(b);
        }
        else{
            if(!a1){
                a1=a,b1=b;
            }
            else{
                a2=a,b2=b;
            }
        }
    }
    dfs1(1);
    v[a1].pb(b1);
    v[b1].pb(a1);
    v[a2].pb(b2);
    v[b2].pb(a2);
    insty(a1,b1,1);
    insty(a2,b2,2);
    jumpandtag(a1,b1,1);
    jumpandtag(a2,b2,2);
    int tty=0;
    for(auto p:ty){
        if(p.se==3)tty=1;
    }
    if(tty)solve1();
    else solve0();
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}