#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define fou(i,st,ed) for (int i=st;i<=ed;i++)
#define fod(i,st,ed) for (int i=st;i>=ed;i--)
#define mymin(x,y) (x<y?x:y)
#define maxn 100000+100
using namespace std;
int lev[maxn],low[maxn],vis[maxn],first[maxn],fa[maxn],bri[maxn];
int N,M,rd,ans,zu;
struct adj_list
{
    int to,next;
}road[maxn*10];
void ins(int from,int to)
{
    rd++;
    road[rd].to=to; road[rd].next=first[from];
    first[from]=rd;
}
void init()
{
    rd=0; memset(first,0,sizeof(first));
    fou (i,1,M)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y); ins(y,x);
    }
}
void dfs(int x,int dep)
{
    vis[x]=1;
    lev[x]=low[x]=dep;
    int flag=1;
    for (int k=first[x];k;k=road[k].next)
    {
        int to=road[k].to;
        if (fa[x]==to && flag)
        {
            flag--;
            continue;
        }
        if (vis[to]==1) low[x]=mymin(low[x],lev[to]);
        else if (vis[to]==0)
        {
            fa[to]=x;
            dfs(to,dep+1);
            low[x]=mymin(low[x],low[to]);
            if (low[to]>lev[x])
            {
                ans++;
                bri[to]=1;
            }
        }
    }
    vis[x]=2;
}
void build()
{
    memset(vis,0,sizeof(vis));
    memset(bri,0,sizeof(bri));
    memset(fa,0,sizeof(fa));
    memset(lev,0,sizeof(lev));
    memset(low,0,sizeof(low));
    fa[1]=1; ans=0;
    dfs(1,0);
}
void LCA(int x,int y)
{
    if (lev[x]<lev[y]) swap(x,y);
    while (lev[x]>lev[y])
    {
        ans-=bri[x];
        bri[x]=0;
        x=fa[x];
    }
    while (x!=y)
    {
        ans-=bri[x]; bri[x]=0;
        ans-=bri[y]; bri[y]=0;
        x=fa[x]; y=fa[y];
    }
}
void solve()
{
    zu++; printf("Case %d:\n",zu);
    int Q; scanf("%d",&Q);
    while (Q-->0)
    {
        int x,y; scanf("%d%d",&x,&y);
        LCA(x,y);
        printf("%d\n",ans);
    }
    puts("");
}
int main()
{
    zu=0;
    while (scanf("%d%d",&N,&M),N)
    {
        init();
        build();
        solve();
    }
    return 0;
}