#include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int MAXN=;

 int bin[MAXN],n,m;

 int low[MAXN],dfn[MAXN],father[MAXN];

 int q,cut,index;

 vector<int>g[MAXN];

 int findx(int x)

 {

     return bin[x]==x?x:(bin[x]=findx(bin[x]));

 }

 int merge(int x,int y)

 {

     int fx,fy;

     fx=findx(x);

     fy=findx(y);

     if(fx!=fy)

     {

         bin[fx]=fy;

         return ;

     }

     else

         return ;

 }

 void tarjan(int i,int pre)

 {

     int j,k;

     low[i]=dfn[i]=++index;

     for (k=; k<g[i].size(); k++)

     {

         j = g[i][k];

         if (!dfn[j])

         {

             tarjan(j,i);

             low[i]=min(low[i],low[j]);

             father[j]=i;

             if (low[j] > dfn[i])

                 cut++;

             else

                 merge(i,j);

         }

         else if (j!=pre)

         {

             low[i]=min(low[i],dfn[j]);

         }

     }

 }

 void lca(int u,int v)

 {

     while (u!=v)

     {

         while (dfn[u]>=dfn[v] && u!=v)

         {

             if (merge(u,father[u]))

                 cut--;

             u = father[u];

         }

         while (dfn[v]>=dfn[u]&&u!=v)

         {

             if (merge(v,father[v]))

                 cut--;

             v=father[v];

         }

     }

 }

 int main()

 {

     int i,x,y,T=;

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

     {

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

         {

             g[i].clear();

             low[i]=dfn[i]=father[i]=;

             bin[i]=i;

         }

         index=cut=;

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

         {

             scanf("%d%d",&x,&y);

             g[x].push_back(y);

             g[y].push_back(x);

         }

         tarjan(,-);

         scanf("%d",&q);

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

         while(q--)

         {

             scanf("%d%d",&x,&y);

             lca(x,y);

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

         }

         cout<<endl;

     }

     return ;

 }