/**

 problem: http://poj.org/problem?id=3694

 问每加一条边后剩下多少桥

 因为是无向图，所以使用tarjan缩点后会成一棵树并维护pre数组

 在树上连一条边(a,b)减少的桥数就是

 a点到a点和b点的最近公共祖先（lca）的所有边+b点到a点和b点的最近公共祖先的所有边

 在算桥的同时将这些点缩成一个点

 即每个点color = 最近公共祖先color

 同时维护pre数组 每个点的pre = 最近公共祖先的pre 即可

 **/

 #include<stdio.h>

 #include<stack>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int MAXN = ;

 const int MAXM = ;

 class Graphics{

 private:

     struct Edge{

         int to, next;

         bool bridge;

     }edge[MAXM];

     struct Point{

         int dfn, low, color;

     }point[MAXN];

     int first[MAXN], pre[MAXN], sign, sumOfPoint, dfnNum, colorNum, bridge;

     bool vis[MAXN];

     stack<int> stk;

     queue<int> bfs;

     void tarjan(int u, int preEdge = -){

         point[u].low = dfnNum;

         point[u].dfn = dfnNum ++;

         vis[u] = true;

         stk.push(u);

         for(int i = first[u]; i != -; i = edge[i].next){

             int to = edge[i].to;

             if((i^) == preEdge) continue;

             if(!point[to].dfn){

                 pre[to] = u; ///如果下一个点没被访问过则更新一下下个点的pre

                 tarjan(to, i);

                 point[u].low = min(point[u].low, point[to].low);

                 if(point[to].low > point[u].dfn){

                     edge[i].bridge = true;

                     edge[i^].bridge = true;

                     bridge ++;

                 }

             }else if(vis[to]){

                 point[u].low = min(point[to].dfn, point[u].low);

             }

         }

         if(point[u].dfn == point[u].low){

             vis[u] = false;

             point[u].color = ++ colorNum;

             while(stk.top() != u){

                 pre[stk.top()] = pre[u]; ///缩点时，该环中的所有点pre等于时间戳最小点的pre

                 point[stk.top()].color = colorNum;

                 vis[stk.top()] = false;

                 stk.pop();

             }

             stk.pop();

         }

     }

 public:

     void clear(int n){

         sumOfPoint = n;

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

             first[i] = -;

             pre[i] = -;

             vis[i] = ;

             point[i].dfn = ;

         }

         sign = colorNum = bridge = ;

         dfnNum = ;

         while(!stk.empty()) stk.pop();

     }

     void addEdgeOneWay(int u, int v){

         edge[sign].to = v;

         edge[sign].next = first[u];

         edge[sign].bridge = false;

         first[u] = sign ++;

     }

     void addEdgeTwoWay(int u, int v){

         addEdgeOneWay(u, v);

         addEdgeOneWay(v, u);

     }

     void tarjanAllPoint(){

         for(int i = ; i <= sumOfPoint; i ++){

             if(!point[i].dfn)

                 tarjan(i);

         }

     }

     int getAns(int a, int b){

         for(int i = ; i <= colorNum; i ++){

             vis[i] = false;

         }

         vis[point[a].color] = true;

         vis[point[b].color] = true;

         int lca, lcacolor, ta = a, tb = b;

         while(true){

             if(ta != -) ta = pre[ta];

             if(tb != -) tb = pre[tb];

             if(vis[point[ta].color]){

                 lcacolor = point[ta].color;

                 lca = ta;

                 break;

             }

             if(vis[point[tb].color]){

                 lcacolor = point[tb].color;

                 lca = tb;

                 break;

             }

             vis[point[ta].color] = true;

             vis[point[tb].color] = true;

         }

         while(point[a].color != lcacolor){

             for(int i = first[a]; i != -; i = edge[i].next){

                 int to = edge[i].to;

                 if(to == pre[a] && edge[i].bridge){

                     bridge --;

                     edge[i].bridge = false;

                     edge[i^].bridge = false;

                     break;

                 }

             }

             point[a].color = lcacolor;

             int tmp = pre[a];

             pre[a] = pre[lca];

             a = tmp;

         }

         while(point[b].color != lcacolor){

             for(int i = first[b]; i != -; i = edge[i].next){

                 int to = edge[i].to;

                 if(to == pre[b] && edge[i].bridge){

                     bridge --;

                     edge[i].bridge = false;

                     edge[i^].bridge = false;

                     break;

                 }

             }

             point[b].color = lcacolor;

             int tmp = pre[b];

             pre[b] = pre[lca];

             b = tmp;

         }

         addEdgeTwoWay(a, b);

         return bridge;

     }

 }graph;

 int main(){

     int n, m, cas = ;

     while(scanf("%d%d", &n, &m) != EOF && m + n){

         graph.clear(n);

         while(m --){

             int a, b;

             scanf("%d%d", &a, &b);

             graph.addEdgeTwoWay(a, b);

         }

         graph.tarjanAllPoint();

         int q;

         scanf("%d", &q);

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

         while(q --){

             int a, b;

             scanf("%d%d", &a, &b);

             printf("%d\n", graph.getAns(a, b));

         }

         putchar('\n');

     }

     return ;

 }