> Var
> 	n, m, l, time, ans, top, Test:longint;
> 	pre, other, opp:array[0..400005] of longint;
> 	vis:array[0..400005] of boolean;
> 	edge:array[0..200005,0..1] of longint;
> 	last, f, fa, depth, dfn, low, zt, color:array[0..100005] of longint;
> 	v:array[0..100005] of boolean;
> 
> procedure Add_edge(p, q:longint);
> begin
> 	inc(l); pre[l] := last[p]; last[p] := l; other[l] := q; opp[l] := l + 1;
> 	inc(l); pre[l] := last[q]; last[q] := l; other[l] := p; opp[l] := l - 1;
> end;
> 
> Procedure Init;
> var
> 	i, p ,q:longint;
> begin
> 	l := 0;
> 	Fillchar(last, sizeof(last), 0);
> 	for i := 1 to m do
> 	begin
> 		read(p, q);
> 		edge[i][0] := p; edge[i][1] := q;
> 		Add_edge(p, q);
> 	end;
> end;
> 
> Procedure Tarjan(p:longint);
> var
> 	q:longint;
> begin
> 	inc(time);
> 	dfn[p] := time; low[p] := time;
> 	inc(top); zt[top] := p; v[p] := true;
> 	q := last[p];
> 	while q <> 0 do
> 	begin
> 		if vis[q] then 
> 		begin
> 			q := pre[q];
> 			continue;
> 		end;
> 		if dfn[other[q]] = -1 then
> 		begin
> 			vis[opp[q]] := true;
> 			Tarjan(other[q]);
> 			if low[other[q]] < low[p] then
> 				low[p] := low[other[q]];
> 			if low[other[q]] > dfn[p] then
> 			begin
> 				inc(ans);
> 				while zt[top] <> p do
> 				begin
> 					color[zt[top]] := ans;
> 					v[zt[top]] := false;
> 					dec(top);
> 				end;
> 			end;
> 		end
> 		else
> 			if dfn[other[q]] < low[p] then
> 				low[p] := dfn[other[q]];
> 		q := pre[q];
> 	end;
> end;
> 
> Procedure Dfs(p, father:longint);
> var
> 	q:longint;
> begin
> 	depth[p] := depth[father] + 1;
> 	q := last[p];
> 	while q <> 0 do
> 	begin
> 		if other[q] <> father then
> 		begin
> 			fa[other[q]] := p;
> 			Dfs(other[q], p);
> 		end;
> 		q := pre[q];
> 	end;
> end;
> 
> Function getf(x:longint):longint;
> begin
> 	if f[x] = x then exit(x);
> 	f[x] := getf(f[x]);
> 	exit(f[x]);
> end;
> 
> Procedure Lca(a, b:longint);
> var
> 	x, y:longint;
> begin
> 	x := getf(a); y := getf(b);
> 	while x <> y do
> 		if depth[x] > depth[y] then
> 		begin
> 			if not v[x] then 
> 			begin
> 				v[x] := true;
> 				dec(ans);
> 			end;
> 			f[x] := getf(fa[x]);
> 			x := getf(x);
> 		end
> 		else
> 		begin
> 			if not v[y] then 
> 			begin
> 				v[y] := true;
> 				dec(ans);
> 			end;
> 			f[y] := getf(fa[y]);
> 			y := getf(y);
> 		end;
> end;
> 
> Procedure Main;
> var
> 	i, query, p, q:longint;
> begin
> 	Fillchar(dfn, sizeof(dfn), 255);
> 	Fillchar(vis, sizeof(vis), 0);
> 	time := 0; ans := 0; top := 0;
> 	Tarjan(1);
> 	if top > 0 then
> 	begin
>         while top > 0 do
>         begin
> 			color[zt[top]] := ans + 1;
> 			dec(top);
> 		end;
>     end;
> 	
> 	l := 0;
> 	Fillchar(last, sizeof(last), 0);
> 	for i := 1 to m do
> 		if color[edge[i][0]] <> color[edge[i][1]] then
> 			Add_edge(color[edge[i][0]], color[edge[i][1]]);
> 	Dfs(1, 0);
> 	
> 	Fillchar(v, sizeof(v), 0);
> 	for i := 1 to n do
> 		f[i] := i;
> 	writeln('Case ', Test, ':');
> 	read(query);
> 	for i := 1 to query do
> 	begin
> 		read(p, q);
> 		Lca(color[p], color[q]);
> 		writeln(ans);
> 	end;
> end;
> 
> Begin
> 	read(n, m);
> 	while (n <> 0) and (m <> 0) do
> 	begin
> 		inc(Test);
> 		Init;
> 		Main;
> 		writeln;
> 		read(n, m);
> 	end;
> End.