rt

#include<bits/stdc++.h>
#define debug cout<<"debug";
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
vector<int>edge[N];
int a[M],b[M],ta[M],tb[M];
int DFN[N],LOW[N],idx;
set<int>s[N];
set<pair<int,int> >st;
int tr[N<<2],tag[N<<2];
int dep[N],sz[N],fa[N],son[N];
int top[N],dfn[N],id;
int scc[N],cnt;
bool vis[N];
void clear()
{
    st.clear();
    idx=id=cnt=0;
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    memset(ta,0,sizeof ta);
    memset(tb,0,sizeof tb);
    for(int i=1;i<=n;++i)
    {
        edge[i].clear();
        s[i].clear();
        DFN[i]=LOW[i]=dep[i]=sz[i]=fa[i]=son[i]=top[i]=dfn[i]=vis[i]=scc[i]=0;
    }
}
void addedge(int k,int u,int v)
{
    if(u>v)swap(u,v);
    a[k]=u,b[k]=v;
    edge[u].emplace_back(v);
    edge[v].emplace_back(u);
}
void tarjan(int u,int fa)
{
    DFN[u]=LOW[u]=++idx;
    for(auto &v:edge[u])
    {
        if(!DFN[v])
        {
            tarjan(v,u);
            LOW[u]=min(LOW[u],LOW[v]);
            if(LOW[v]>DFN[u])
            {
                s[u].emplace(v);
                s[v].emplace(u);
            }
        }
        else if(v!=fa)
            LOW[u]=min(LOW[u],DFN[v]);
    }
}
void dfs(int u)
{
    if(vis[u])
        return ;
    vis[u]=1;
    scc[u]=cnt;
    for(auto &v:edge[u])
        if(s[u].find(v)==s[u].end())
            dfs(v);
}
void dfs1(int u,int f)
{
    dep[u]=dep[f]+1;
    fa[u]=f;
    sz[u]=1;
    son[u]=-1;
    for(auto &v:edge[u])
    {
        if(v==f)
            continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(son[u]==-1||sz[v]>sz[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int t)
{
    top[u]=t;
    dfn[u]=++id;
    if(~son[u])
        dfs2(son[u],t);
    for(auto &v:edge[u])
        if(v!=fa[u]&&v!=son[u])
            dfs2(v,v);
}
void pushup(int p){tr[p]=tr[p<<1]+tr[p<<1|1];}
void addtag(int p,int pl,int pr,int d)
{
    tr[p]=(pr-pl+1)*d;
    tag[p]=d;
}
void pushdown(int p,int pl,int pr)
{
    int mid=(pl+pr)>>1;
    if(~tag[p])
    {
        addtag(p<<1,pl,mid,tag[p]);
        addtag(p<<1|1,mid+1,pr,tag[p]);
        tag[p]=-1;
    }
}
void build(int p,int pl,int pr)
{
    tag[p]=-1;
    if(pl==pr)
        return ;
    int mid=(pl+pr)>>1;
    build(p<<1,pl,mid);
    build(p<<1|1,mid+1,pr);
    pushup(p);
}
void update(int p,int pl,int pr,int L,int R,int d)
{
    if(R<pl||pr<L)
        return ;
    if(L<=pl&&pr<=R)
        return addtag(p,pl,pr,d);
    pushdown(p,pl,pr);
    int mid=(pl+pr)>>1;
    update(p<<1,pl,mid,L,R,d);
    update(p<<1|1,mid+1,pr,L,R,d);
    pushup(p);
}
int query(int p,int pl,int pr,int L,int R)
{
    if(R<pl||pr<L)
        return 0;
    if(L<=pl&&pr<=R)
        return tr[p];
    pushdown(p,pl,pr);
    int mid=(pl+pr)>>1;
    return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);
}
void rebuild()
{
    for(int i=1;i<=n;++i)
        if(!DFN[i])
            tarjan(i,0);
    for(int i=1;i<=n;++i)
        if(!vis[i])
            ++cnt,dfs(i);
    for(int i=1;i<=n;++i)
        edge[i].clear();
    int tot=0;
    for(int i=1;i<=n;++i)
        if(st.find(make_pair(a[i],b[i]))==st.end())
        {
            st.emplace(make_pair(a[i],b[i]));
            edge[a[i]].emplace_back(b[i]);
            edge[b[i]].emplace_back(a[i]);
            ta[++tot]=a[i];
            tb[tot]=b[i];
        }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,cnt);
    for(int i=1;i<=tot;++i)
    {
        int u=ta[i],v=tb[i];
        if(dep[u]<dep[v])
            swap(u,v);
        update(1,1,cnt,dfn[u],dfn[u],1);
    }
}

void solve()
{
    clear();
    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin>>u>>v;
        addedge(i,u,v);
    }
    rebuild();
    int q;
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        int x=u,y=v;
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]])
                swap(x,y);
            update(1,1,cnt,dfn[top[x]],dfn[x],0);
            x=fa[top[x]];
        }
        if(dep[x]<dep[y])
            swap(x,y);
        update(1,1,cnt,dfn[y]+1,dfn[x],0);
        cout<<query(1,1,cnt,1,cnt)<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=0;
    while(cin>>n>>m&&n&&m)
    {
        ++T;
        cout<<"Case "<<T<<":\n";
        solve();
        cout<<'\n';
    }
}