#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define MAXN 100009

 #pragma comment(linker,"/STACk:10240000,10240000")

 int n,m,cnt,NE,BridgeNum;

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

 bool mark[MAXN],isbridge[MAXN];

 vector<int>ve[MAXN];

 void Tarjan(int u,int father)

 {

     int flag=;

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

     mark[u]=true;

     int l=ve[u].size();

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

     {

         int v=ve[u][i];

         if(v==father&&!flag)

         {

             flag=;

             continue;

         }

         if(dfn[v]==)

         {

             parent[v]=u;

             Tarjan(v,u);

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

             if(low[v]>dfn[u])

             {

                 isbridge[v]=;

                 BridgeNum++;

             }

         }

         else if(mark[v])

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

     }

 }

 void LCA(int u,int v)

 {

     while(dfn[u]>dfn[v])

     {

         if(isbridge[u])

         {

             BridgeNum--;

             isbridge[u]=;

         }

         u=parent[u];

     }

     while(dfn[v]>dfn[u])

     {

         if(isbridge[v])

         {

             BridgeNum--;

             isbridge[v]=;

         }

         v=parent[v];

     }

     while(u!=v)

     {

         if(isbridge[u])

         {

             BridgeNum--;

             isbridge[u]=;

         }

         if(isbridge[v])

         {

             BridgeNum--;

             isbridge[v]=;

         }

         u=parent[u],v=parent[v];

     }

 }

 int main()

 {

     int u,v,Q,ca=;

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

     {

         BridgeNum=NE=cnt=;

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

             ve[i].clear();

         while(m--)

         {

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

             ve[u].push_back(v);

             ve[v].push_back(u);

         }

         memset(isbridge,,sizeof isbridge);

         memset(dfn,,sizeof dfn);

         memset(mark,,sizeof mark);

         for(int i=; i<=n+; i++)parent[i]=i;

         Tarjan(,-);

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

         scanf("%d",&Q);

         while(Q--)

         {

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

             LCA(u,v);

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

         }

         printf("\n");

     }

     return ;

 }