#include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 struct node

 {

     int to, next;

 } edge[*maxn], Edge[*maxn];

 int head[maxn], low[maxn], dfn[maxn], id[maxn], Head[maxn], Father[maxn];

 int pre[maxn], deep[maxn], stack[maxn], tot, ntime, top, cnt, Tot;

 void init ()

 {

     Tot = tot = ntime = top = cnt = ;

     memset (id, , sizeof(id));

     memset (low, , sizeof(low));

     memset (dfn, , sizeof(dfn));

     memset (pre, , sizeof(pre));

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

     memset (deep, , sizeof(deep));

     memset (Head, -, sizeof(Head));

 }

 void Add (int from, int to)

 {

     Edge[Tot].to = to;

     Edge[Tot].next = Head[from];

     Head[from] = Tot++;

 }

 void add (int from, int to)

 {

     edge[tot].to = to;

     edge[tot].next = head[from];

     head[from] = tot++;

 }

 int find (int x)

 {

     if (x != Father[x])

         Father[x] = find(Father[x]);

     return Father[x];

 }

 void dfs (int u, int father, int d)

 {

     pre[u] = father;

     deep[u] = d;

     for (int i=Head[u]; i!=-; i=Edge[i].next)

     {

         int v = Edge[i].to;

         if (father != v)

             dfs (v, u, d+);

     }

 }

 int LCA (int a, int b)

 {

     while (a != b)

     {

         if (deep[a] > deep[b])

             a = pre[a];

         else if (deep[a] < deep[b])

             b = pre[b];

         else

         {

             a = pre[a];

             b = pre[b];

         }

         a = find (a);

         b = find (b);

     }

     return a;

 }

 void Tarjan (int u, int father)

 {

     int k = ;

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

     stack[top ++] = u;

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

     {

         int v = edge[i].to;

         if (father == v && !k)

         {

             k ++;

             continue;

         }

         if (!dfn[v])

         {

             Tarjan (v, u);

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

         }

         else

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

     }

     if (low[u] == dfn[u])

     {

         cnt ++;

         while ()

         {

             int v = stack[--top];

             id[v] = cnt;

             if (v == u)

                 break;

         }

     }

 }

 void solve (int n)

 {

     Tarjan (, );

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

         for (int j=head[i]; j!=-; j=edge[j].next)

         {

             int u = id[i];

             int v = id[edge[j].to];

             if (u != v)

                 Add (u, v);

         }

     dfs (, , );

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

         Father[i] = i;

     int q;

     cnt --;

     scanf ("%d", &q);

     while (q --)

     {

         int u, v;

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

         u = find(id[u]);

         v = find(id[v]);

         int lca = LCA(u, v);

         while (u != lca)

         {

             cnt --;

             Father[u] = lca;

             u = find (pre[u]);

         }

         while (v !=lca)

         {

             cnt --;

             Father[v] = lca;

             v = find (pre[v]);

         }

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

     }

 }

 int main ()

 {

     int n, m, l = ;

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

     {

         init ();

         while (m --)

         {

             int u, v;

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

             add (u, v);

             add (v, u);

         }

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

         solve (n);

         printf ("\n");

     }

     return ;

 }