const
  maxq=1000;
  maxn=100000;
  maxm=200000;
  start=1;

type
  pointer=^Rec;
  rec=record
    k,num,me:longint;
    next:pointer;
  end;

var
  n,m,q,ii:longint;
  ans:array[start..maxq]of longint;
  deep,r,father:array[start..maxn]of longint;
  que:array[start..maxq,1..2]of longint;
  edge:array[start..maxm,1..2]of longint;
  link,link_r,link2,ro:array[start..maxn]of pointer;
  cover:array[start..maxn]of boolean;
  cover_m:array[start..maxm]of boolean;

    procedure creat(i,j,k:longint);
    var
      p:pointer;
    begin
      new(p); p^.k:=k; p^.me:=j; p^.num:=i; p^.next:=link[j]; link[j]:=p;
    end;

    procedure creat2(i,j,k:longint);
    var
      p:pointer;
    begin
      new(p); p^.k:=k; p^.num:=i; p^.next:=link2[j]; p^.me:=j; link2[j]:=p;
    end;

  procedure init;
  var
    p,p2:pointer;
    i,j,k:longint;
  begin
    readln(n,m);
    if n=0 then halt;
    for i:=1 to n do
      begin
        p:=link[i];
        while p<>nil do
          begin
            p2:=p^.next;
            dispose(p);
            p:=p2;
          end;
      end;
    for i:=1 to n do
      begin
        p:=link_r[i];
        while p<>nil do
          begin
            p2:=p^.next;
            dispose(p);
            p:=p2;
          end;
      end;
    for i:=1 to n do ro[i]:=nil;
    for i:=1 to n do link2[i]:=nil;
    for i:=1 to n do link_r[i]:=nil;
    for i:=1 to n do link[i]:=nil;
    for i:=1 to m do
      begin
        readln(j,k);
        edge[i,1]:=j;
        edge[i,2]:=k;
        if j=k then continue;
        creat(i,j,k);
        creat(i,k,j);
      end;
    readln(q);
    for i:=1 to q do
      begin
        readln(que[i,1],que[i,2]);
        creat2(i,que[i,1],que[i,2]);
        creat2(i,que[i,2],que[i,1]);
      end;
  end;

    procedure find(i,d:longint);
    var
      p:pointer;
    begin
      deep[i]:=d;
      cover[i]:=true;
      p:=link[i];
      while p<>nil do
        begin
          if not cover_m[p^.num] then
            begin
              if not cover[p^.k] then
                begin
                  cover_m[p^.num]:=true;
                  find(p^.k,d+1);
                end;
              if deep[p^.k]<=deep[i] then
                begin
                  r[i]:=r[p^.k];
                  deep[i]:=deep[p^.k];
                end;
            end;
          p:=p^.next;
        end;
    end;

    function get_f(i:longint):longint;
    var
      p:pointer;
    begin
      cover[i]:=true;
      if r[i]=i then
        get_f:=i else
      begin
        get_f:=get_f(r[i]);
        r[i]:=get_f;
      end;
    end;

    function getfather(i:longint):longint;
    begin
      if father[i]=i then exit(i);
      getfather:=getfather(father[i]);
      father[i]:=getfather;
    end;

    procedure LCA(i:longint);
    var
      p,p2:pointer;
    begin
      cover[i]:=true;
      p:=link_r[i];
      while p<>nil do
        begin
          p2:=link2[p^.k];
          while p2<>nil do
            begin
              if cover[r[p2^.k]] then
                begin
                  ans[p2^.num]:=getfather(r[p2^.k]);
                end;
              {if not cover[r[p2^.k]] then
                begin
                  LCA(r[p2^.k]);
                  ro[r[p2^.k]]:=p2;
                  father[r[p2^.k]]:=i;
                end;}
              p2:=p2^.next;
            end;
          p:=p^.next;
        end;
      p:=link_r[i];
      while p<>nil do
        begin
          p2:=link[p^.k];
          while p2<>nil do
            begin
              if not cover[r[p2^.k]] then
                begin
                  LCA(r[p2^.k]);
                  ro[r[p2^.k]]:=p2;
                  father[r[p2^.k]]:=i;
                end;
              p2:=p2^.next;
            end;
          p:=p^.next;
        end;
    end;

    function check(i,a:longint):longint;
    var
      p:pointer;
    begin
      check:=0;
      if (i=a)or(father[i]=father[a]) then exit;
      p:=ro[father[i]];
      repeat
        if check<>0 then p:=ro[r[p^.me]];
        inc(check);
        father[r[p^.k]]:=a;
      until father[r[p^.me]]=a;
    end;

  procedure main;
  var
    p:pointer;
    i,nn,j,k,jj,kk:longint;
  begin
    fillchar(deep,sizeof(deep),0);
    fillchar(cover,sizeof(cover),false);
    fillchar(cover_m,sizeof(cover_m),false);
    for i:=1 to n do r[i]:=i;
    find(1,0);
    fillchar(cover,sizeof(cover),false);
    for i:=1 to n do if not cover[i] then get_f(i);
    for i:=1 to n do
      begin
        new(p); p^.k:=i; p^.next:=link_r[r[i]]; link_r[r[i]]:=p;
      end;
    for i:=1 to n do father[i]:=i;
    fillchar(cover,sizeof(cover),false);
    LCA(1);
    nn:=0;
    fillchar(cover,sizeof(cover),false);
    for i:=1 to n do cover[r[i]]:=true;
    for i:=1 to n do if cover[i] then inc(nn);
    dec(nn);
    for i:=1 to n do father[i]:=i;
    for i:=1 to q do
      begin
        j:=r[que[i,1]]; k:=r[que[i,2]];
        jj:=check(j,ans[i]);
        kk:=check(k,ans[i]);
        nn:=nn-jj-kk;
        writeln(nn);
      end;
  end;

begin
  ii:=0;
  while true do
    begin
      init;
      inc(ii);
      if ii<>1 then writeln;
      writeln('Case ',ii,':');
      main;
    end;
end.