prob

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=2e5+5;
int a[M],b[M];
vector<int>edge[N];
set<int>cut[N];
int Dfn[N],Low[N],Id;
void tarjan(int u,int fa)
{
    Dfn[u]=Low[u]=++Id;
    for(auto &v:edge[u])
    {
        if(v==fa)continue;
        if(!Dfn[v])
        {
            tarjan(v,u);
            Low[u]=min(Low[u],Low[v]);
            if(Low[v]>Dfn[u])
            {
                cut[u].emplace(v);
                cut[v].emplace(u);
            }   
        }
        else
            Low[u]=min(Low[u],Dfn[v]);
    }
}
bool vis[N];
int fa[N],cnt;
void dfs(int u)
{
    if(vis[u])return;
    vis[u]=1;
    fa[u]=cnt;
    for(auto &v:edge[u])
    {
        if(cut[u].find(v)!=cut[u].end())
            continue;
        dfs(v);
    }
}
int f[N],sz[N],son[N],dep[N];
int dfn[N],top[N],id;
void dfs1(int u,int fat)
{
    f[u]=fat;
    dep[u]=dep[fat]+1;
    sz[u]=1;
    son[u]=-1;
    for(auto &v:edge[u])
    {
        if(v==fat)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)
{
    dfn[u]=++id;
    top[u]=t;
    if(~son[u])dfs2(son[u],t);
    for(auto &v:edge[u])
    {
        if(v==f[u]||v==son[u])
            continue;
        dfs2(v,v);
    }
}
int tr[N<<2],tag[N<<2];
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)
{
    if(~tag[p])
    {
        int mid=(pl+pr)>>1;
        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)
    {
        addtag(p,pl,pr,d);
        return ;
    }
    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);
}
int n,m;
void clear()
{
    memset(tr,0,sizeof tr);
    memset(tag,0,sizeof tag);
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    memset(Dfn,0,sizeof Dfn);
    memset(Low,0,sizeof Low);
    Id=0;memset(vis,0,sizeof vis);

    memset(fa,0,sizeof fa);
    cnt=0;
    memset(f,0,sizeof f);
    memset(sz,0,sizeof sz);
    memset(son,0,sizeof son);
    memset(dep,0,sizeof dep);
    memset(top,0,sizeof top);
    memset(dfn,0,sizeof dfn);
    id=0;
    for(int i=1;i<=n;++i)
    {
        edge[i].clear();
        cut[i].clear();
    }
}
void solve()
{
    clear();
    for(int i=1;i<=m;++i)
    {
        cin>>a[i]>>b[i];
        edge[a[i]].emplace_back(b[i]);
        edge[b[i]].emplace_back(a[i]);
    }
    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();
    for(int i=1;i<=m;++i)
    {
        if(fa[a[i]]==fa[b[i]])continue;
        edge[fa[a[i]]].emplace_back(fa[b[i]]);
        edge[fa[b[i]]].emplace_back(fa[a[i]]);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,cnt);
    for(int i=1;i<=m;++i)
    {
        int x=fa[a[i]],y=fa[b[i]];
        if(x==y)continue;
        if(dep[x]<dep[y])swap(x,y);
        update(1,1,n,dfn[x],dfn[x],1);
    }
    int q;
    for(cin>>q;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=f[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        update(1,1,cnt,dfn[x]+1,dfn[y],0);
        cout<<tr[1]<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int caseCount=0;
    while(cin>>n>>m&&n&&m)
    {
        cout<<"Case "<<++caseCount<<":\n";
        solve();
        cout<<'\n';
    }
}