#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<pair<int,int>>G1[N];
vector<int>G2[N];
 
int tsp,cnt,dfn[N],low[N],scc[N];
stack<int>stk;bool instk[N];

void tarjan(int x, int in_id) 
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);instk[x]=1;
    for(auto i:G1[x]) if(i.second!=in_id)
	{
        int y=i.first,id=i.second;
        if(dfn[y]==0) 
		{
            tarjan(y,id);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
	    cnt++;
	    for(int z=-1;z!=x;)
	    {
	    	z=stk.top();stk.pop();instk[z]=0;
	    	scc[z]=cnt;
	    }
	}
}

int ans,fa[N]/*并查集中的父节点*/, dep[N]/*缩点之后的树上的深度*/, up[N]/*缩点之后的树上的父节点*/;
void dfs_scc(int x) 
{
    for(int y:G2[x])if(dep[y]==0)
    {
        dep[y]=dep[x]+1;
        up[y] =x;
        dfs_scc(y);
    }
}
 
int findfa(int x){ return (x==fa[x]) ? x : (fa[x] = findfa(fa[x]));}
void solve(int x,int y)
{
    x=findfa(x),y=findfa(y);
    while(x!=y)
    {
        if(dep[x]<dep[y])swap(x,y);
        ans--;// x到up[x]的边从桥边变为非桥边
        fa[x]=findfa(up[x]);//不能是：fa[x] = up[x];
        x=findfa(x);//此处也可以：x = fa[x];
    }
}
 
int main()
{
    int T=0,n,m;
    while(scanf("%d%d",&n,&m)!=EOF && !(n==0 && m==0) ) 
    {
        memset(G1,0,sizeof(G1));
        for(int i=1,x,y;i<=m;i++)
        {
            scanf("%d%d", &x,&y);
            G1[x].push_back({y,i});
            G1[y].push_back({x,i});
        }
         
        tsp=cnt=0;memset(low,0,sizeof low);memset(dfn,0,sizeof dfn);
		memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
        tarjan(1, 0);
         
        memset(G2,0,sizeof(G2));
        map<pair<int,int>,bool>mp;
        for(int i=1;i<=n;i++)for(auto j:G1[i])
        {
            int x=scc[i], y=scc[j.first];if(x>y)swap(x,y);
            if(x!=y && !mp[{x,y}])
            {
                G2[x].push_back(y);
                G2[y].push_back(x);
                mp[{x,y}]=1;
            }
        }
         
        memset(up,0,sizeof(up));memset(dep, 0, sizeof(dep));
        dep[1]=1,dfs_scc(1);
         
        for(int i=1;i<=cnt;i++) fa[i]=i;
        printf("Case %d:\n",++T);
        int q;scanf("%d",&q);
        ans=cnt-1;
        while(q--)
        {
            int x,y;scanf("%d%d",&x,&y);
            x=scc[x],y=scc[y];
            if(x!=y) solve(x,y);
            printf("%d\n", ans);
        }
        printf("\n");
    }
    return 0;
}