#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <queue>

#include <algorithm>

#include <vector>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

const int maxn = , INF = 0x7fffffff;

int pre[maxn], f[maxn], pa[maxn];

int dfs_clock;

int n, m, ret;

vector<int> G[maxn];

int find(int x)

{

    return f[x]==x?x:(f[x]=find(f[x]));

}

int Union(int u, int v)

{

    int r = find(u);

    int l = find(v);

    if(r == l) return ;

    f[r] = l;

    return ;

}

int dfs(int u, int fa)

{

    pa[u] = fa;

    int lowu = pre[u] = ++dfs_clock;

    for(int i=; i<G[u].size(); i++)

    {

        int v = G[u][i];

        if(!pre[v])

        {

     //       pa[v] = u;

            int lowv = dfs(v, u);

            lowu = min(lowu, lowv);

            if(lowv > pre[u])

                ret++;

            else

                Union(u, v);   //如果u和v之间没桥，那么u和v就同属于一个集合

        }

        else if(pre[v] < pre[u] && v != fa)

            lowu = min(lowu, pre[v]);

    }

    return lowu;

}

int lca(int u, int v)

{

    int r = find(u);

    int l = find(v);

    if(r == l)

        return ret;

    if(pre[u] > pre[v])

        swap(u, v);

    while(pre[u] < pre[v])

    {

        if(Union(pa[v], v))

            ret--;

        v = pa[v];

    }

    while(u != v)     //v经过上一个while后要么是u 要么是u和v的最近公共祖先

    {

        if(Union(u, pa[u]))

            ret--;

        u = pa[u];

    }

    return ret;

}

void init()

{

    mem(pre, );

    mem(pa, );

    for(int i=; i<=n; i++) f[i] = i;

    dfs_clock = ;

    ret = ;

}

int main()

{

    int kase = ;

    while(cin>> n >> m && n+m)

    {

        init();

        for(int i=; i<m; i++)

        {

            int u, v;

            cin>> u >> v;

            G[u].push_back(v);

            G[v].push_back(u);

        }

        dfs(, -);

        int Q;

        cin>> Q;

        printf("Case %d:\n",++kase);

        for(int i=; i<Q; i++)

        {

            int u, v;

            cin>> u >> v;

            cout<< lca(u, v) <<endl;

        }

    }

    return ;

}