#include <iostream>

 #include <algorithm>

 #include <cstdio>

 using namespace std;

 const int N = 1e5 + , M = 2e5 + ;

 int head[N], ver[M * ], Next[M * ];

 int dfn[N], low[N], n, m, tot, num;

 bool bridge[M * ];

 void add(int x, int y)

 {

     ver[++tot] = y, Next[tot] = head[x], head[x] = tot;

 }

 void tarjan(int x, int in_edge)

 {

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

     for(int i = head[x]; i; i = Next[i])

     {

         int y = ver[i];

         if(!dfn[y])

         {

             tarjan(y, i); ///节点 和 入边

             low[x] = min(low[x], low[y]);

             if(low[y] > dfn[x])

             {

                 bridge[i] = bridge[i ^ ] = true;

             }

         }

         else if(i != (in_edge ^ )) ///搜索树上的边

         {

             low[x] = min(low[x], dfn[y]);

         }

     }

 }

 int c[N], dcc;

 void dfs(int x)

 {

     c[x] = dcc;

     for(int i = head[x]; i; i = Next[i])

     {

         int y = ver[i];

         if(c[y] || bridge[i]) continue;

         dfs(y);

     }

 }

 const int maxn = N;

 ///加边

 int cnt, h[maxn];

 struct edge

 {

     int to, pre, v;

 } e[maxn << ];

 void add(int from, int to, int v)

 {

     cnt++;

     e[cnt].pre = h[from]; ///5-->3-->1-->0

     e[cnt].to = to;

     e[cnt].v = v;

     h[from] = cnt;

 }

 ///LCA

 int dist[maxn];

 int dep[maxn];

 int anc[maxn][]; ///2分的父亲节点

 void dfs(int u, int fa)

 {

     for(int i = h[u]; i; i = e[i].pre)

     {

         int v = e[i].to;

         if(v == fa) continue;

         dist[v] = dist[u] + e[i].v;

         dep[v] = dep[u] + ;

         anc[v][] = u;

         dfs(v, u);

     }

 }

 void LCA_init(int n)

 {

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

         for(int i = ; i <= n; i++) if(anc[i][j-])

         anc[i][j] = anc[anc[i][j-]][j-];

 }

 int LCA(int u, int v)

 {

     int log;

     if(dep[u] < dep[v]) swap(u, v);

     for(log = ; ( << log) < dep[u]; log++);

     for(int i = log; i >= ; i--)

         if(dep[u] - ( << i) >= dep[v]) u = anc[u][i];

     if(u == v) return u;

     for(int i = log; i >= ; i--)

         if(anc[u][i] && anc[u][i] != anc[v][i])

             u = anc[u][i], v = anc[v][i];

     return anc[u][];

 }

 int fa[N];

 int Find(int x)

 {

     if(x == fa[x]) return x;

     return fa[x] = Find(fa[x]);

 }

 int main()

 {

     int kase = ;

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

     {

         if(n ==  && m == ) break;

         tot = , dcc = , cnt = ;

         for(int i = ; i <= n; i++) head[i] = , dfn[i] = , low[i] = , c[i] = , h[i] = ;

         for(int i = ; i <= m *  + ; i++) ver[i] = , Next[i] = , bridge[i] = false;

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

         {

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

             add(x, y), add(y, x);

         }

         ///求桥

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

         {

             if(!dfn[i]) tarjan(i, );

         }

         ///求边双连通分量

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

         {

             if(!c[i])

             {

                 ++dcc;

                 dfs(i);

             }

         }

         ///缩点

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

         {

             int x = ver[i ^ ], y = ver[i];

             if(c[x] == c[y]) continue;

             add(c[x], c[y], );

         }

         dfs(, );

         LCA_init(dcc);

         ///并查集初始化

         for(int i = ; i <= dcc; i++) fa[i] = i;

         int Q; scanf("%d", &Q);

         int ans = dcc - ;

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

         while(Q--)

         {

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

             x = c[x], y = c[y];

             int p = LCA(x, y);

             x = Find(x);

             while(dep[x] > dep[p])

             {

                 fa[x] = anc[x][];

                 ans--;

                 x = Find(x);

             }

             y = Find(y);

             while(dep[y] > dep[p])

             {

                 fa[y] = anc[y][];

                 ans--;

                 y = Find(y);

             }

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

         }

     }

     return ;

 }