#include<iostream>

 #include<stack>

 #include<queue>

 #include<map>

 #include<stdio.h>

 #include<cstring>

 #include<string>

 #include<iomanip>

 #include<vector>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 # define ll long long

 # define maxn +

 # define inf 0x3f3f3f3f

 int head[maxn],dfn[maxn],low[maxn];

 int judge[maxn];

 int father[maxn];

 int edge,num,n,m,ans;

 struct node

 {

     int to;

     int nex;

 } q[maxn];

 void init()

 {

     memset(judge,,sizeof(judge));

     memset(head,-,sizeof(head));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     for(int i=; i<=n; i++)

     {

         father[i]=i;

     }

     edge=;

     num=;

     ans=;

 }

 void addedge(int fr,int to)

 {

     q[edge].to=to;

     q[edge].nex=head[fr];

     head[fr]=edge++;

 }

 void tarjan(int u,int root)

 {

     low[u]=dfn[u]=++num;

     dfn[u]=dfn[root]+;//建造树的过程。

     for(int i=head[u]; i!=-; i=q[i].nex)

     {

         int temp=q[i].to;

         if(temp==root)continue;//如果 1-> 2 这条边已经访问过的话，2->1 就没有必要访问了，如果在访问的话会出问题的。

         if(dfn[temp]==)

         {

             father[temp]=u;

             tarjan(temp,u);

             low[u]=min(low[u],low[temp]);

             if(low[temp]>dfn[u])//判断桥的方法，注意比较的是前一个的时间戳

             {

                 ans++;

                 judge[temp]=;

             }

         }

         else if(temp!=u)

         {

             low[u]=min(low[u],dfn[temp]);

         }

     }

 }

 void lca(int t1,int t2)

 {

     while(dfn[t1]<dfn[t2])

     {

         if(judge[t2])ans--,judge[t2]=;

         t2=father[t2];

     }

     while(dfn[t1]>dfn[t2])

     {

         if(judge[t1])

         {

             ans--;

             judge[t1]=;

         }

         t1=father[t1];

     }

     while(t1!=t2)

     {

         if(judge[t1])ans--;

         if(judge[t2])ans--;

         judge[t1]=;

         judge[t2]=;

         t1=father[t1];

         t2=father[t2];

     }

 }

 int main()

 {

     int Case=;

     while(~scanf("%d %d",&n,&m)&&(n+m))

     {

         init();

         int t1,t2;

         for(int i=; i<=m; i++)

         {

             scanf("%d %d",&t1,&t2);

             addedge(t1,t2);

             addedge(t2,t1);

         }

         tarjan(,);

         int t;

         printf("Case %d:\n",++Case);

         scanf("%d",&t);

         while(t--)

         {

             scanf("%d %d",&t1,&t2);

             lca(t1,t2);

             printf("%d\n",ans);

         }

         printf("\n");

     }

     return ;

 }