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.

• Re:RE到死啊！求大牛解答啊！ (14) 455462586 2013-07-22 20:48:14
• Re:RE到死啊！求大牛解答啊！ (3351) 1340502116 2016-01-28 15:51:24