#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=1e5+10;

set<pii>cedges;
vector<int>vect[maxn];
int cycdeg[maxn],color[maxn],pos[maxn],color_merged[maxn],comp_cdeg[maxn];
int n,q;

void fcyc(int x,int prv,vector<int>&stek){

    pos[x]=1;
    stek.pb(x);
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(id==prv)continue;
        if(pos[id]==1){

            cedges.insert({min(x,id),max(x,id)});
            int goal=id;
            /*for(int i=0;i<stek.size();i++){
                printf("%d ",stek[i]);
            }
            printf(" STEK\n");*/
            for(int i=stek.size()-2;i>=0;i--){
                cedges.insert({min(stek[i],stek[i+1]),max(stek[i],stek[i+1])});
                if(stek[i]==goal)break;
            }
            continue;
        }
        if(pos[id])continue;
        fcyc(id,x,stek);
    }

    pos[x]=2;
    stek.pop_back();
}
int cmask[maxn];
int cyc_color[maxn];
void bojaj_dfs(int x,int cl){

    pos[x]=1;
    color[x]=cl;
    cmask[cl]|=cyc_color[x];
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(pos[id] || (cycdeg[id]>0 && cycdeg[x]>0))continue;
        bojaj_dfs(id,cl);
    }
}
void obojaj(){

    memset(pos,0,sizeof(pos));
    for(int i=1;i<=n;i++){
        if(cycdeg[i]==0 || pos[i])continue;
        bojaj_dfs(i,i);
    }

}
void bojaj_dfs_merged(int x,int cl){

    pos[x]=1;
    color_merged[x]=cl;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(pos[id] || cycdeg[id]==3)continue;
        bojaj_dfs_merged(id,cl);
    }
}
void obojaj_merged(){

    memset(pos,0,sizeof(pos));
    for(int i=1;i<=n;i++){
        if(cycdeg[i]==3 || pos[i])continue;
        bojaj_dfs_merged(i,i);
    }

}
void go_merge(){

    obojaj();
    obojaj_merged();

    while(q--){

        int u,v;
        scanf("%d %d",&u,&v);

        if(color[u]==color[v])printf("1\n");
        else{

            u=color[u];
            v=color[v];
            if(cycdeg[u]>cycdeg[v])swap(u,v);

            if(cycdeg[u]==3 && cycdeg[v]==3)printf("3\n");
            else if(cycdeg[u]==2 && cycdeg[v]==3)printf("3\n");
            else{
                if(color_merged[u]==color_merged[v])printf("3\n");
                else printf("4\n");
            }

        }

    }

}
void dfs_cikluse(int x,int prv,int cl){

    cyc_color[x]|=(1<<cl);
    pos[x]=1;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(pos[id] || cycdeg[id]==0 || (cycdeg[x]==4) )continue;
        dfs_cikluse(id,x,cl);
    }

}
void obojaj_cikluse(){

    memset(pos,0,sizeof(pos));
    int cnt=1;
    for(int i=1;i<=n;i++){
        if(pos[i] || cycdeg[i]==0 || cycdeg[i]==4)continue;
        dfs_cikluse(i,0,cnt);
        cnt++;
    }

}
void go_split(){

    obojaj_cikluse();
    obojaj();

    while(q--){

        int u,v;
        scanf("%d %d",&u,&v);

        if(color[u]==color[v])printf("1\n");
        else{

            u=color[u];
            v=color[v];

            ///printf("%d %d AAAA\n",cmask[u],cmask[v]);

            if(cmask[u]&cmask[v])printf("2\n");
            else printf("4\n");

        }

    }


}
int main(){


    ///freopen("test.txt","r",stdin);

    scanf("%d %d",&n,&q);
    for(int i=1;i<=n+1;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        vect[u].pb(v);
        vect[v].pb(u);
    }

    vector<int>stek;
    fcyc(1,0,stek);

    for(set<pii>::iterator it=cedges.begin();it!=cedges.end();it++){
        cycdeg[(*it).ff]++;
        cycdeg[(*it).ss]++;
        ///printf("%d %d CEDGE\n",(*it).ff,(*it).ss);
    }

    int cas=0;
    for(int i=1;i<=n;i++)if(cycdeg[i]==3)cas=1;

    if(cas==1)go_merge();
    else go_split();


    return 0;
}