/*
    不错一道题
    题意：给出一幅图，里面有桥，给出Q个操作，    每个操作会添加一条边，问每次操作后图中桥的个数
    每次求桥会太慢
    考虑一下dfs树，树边肯定是桥，然后每连上x,y，就会形成一个环，这个环内的边就全部都不是割边
    所以只要找到x,y的lca，把这个路径上的桥标记为否即可
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=100010;

inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}

struct Node{
    int v,next;
}nodes[MAXN*10];

int G[MAXN];
int level[MAXN],low[MAXN];
int vi[MAXN],fa[MAXN];
int cut[MAXN],isBridge[MAXN];
int alloc,n,m,bridgeNum;

void add(int a,int b){
    alloc++;
    nodes[alloc].v=b,nodes[alloc].next=G[a];
    G[a]=alloc;
}

void dfs(int u,int dep){
    vi[u]=1;
    level[u]=low[u]=dep;
    bool flag=true;
    //if(u!=1)cut[u]++;
    for(int son=G[u];son;son=nodes[son].next){
        int v=nodes[son].v;
        if(v==fa[u]&&flag){
            flag=false;
            continue;
        }
        if(vi[v]==1)
            low[u]=min(low[u],level[v]);
        else if(vi[v]==0){
            fa[v]=u;
            dfs(v,dep+1);
            low[u]=min(low[u],low[v]);
            //if(low[v]>=level[u])cut[u]++;
            if(low[v]>level[u]){//bridge
                isBridge[v]=1;
                bridgeNum++;
            }
        }
    }
    vi[u]=2;
}
void lca(int x,int y){
    if(level[x]<level[y])swap(x,y);
    while(level[x]>level[y]){
        if(isBridge[x]){
            bridgeNum--;
            isBridge[x]=0;
        }
        x=fa[x];
    }
    while(x!=y){
        if(isBridge[x]){bridgeNum--;isBridge[x]=0;}
        if(isBridge[y]){bridgeNum--;isBridge[y]=0;}
        x=fa[x];y=fa[y];
    }
}
int main(){
    //freopen("in","r",stdin);
    int a,b,t=1;
    while(scanf("%d%d",&n,&m),n){
        alloc=0;
        memset(G+1,0,sizeof(int)*n);
        while(m--){
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        memset(vi,0,sizeof(vi));
        memset(isBridge,0,sizeof(isBridge));
        bridgeNum=0;
        fa[1]=1;
        dfs(1,0);
        printf("Case %d:\n",t++);
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&a,&b);
            lca(a,b);
            printf("%d\n",bridgeNum);
        }
        puts("");
    }
    return 0;
}