I got trapped with your test #1. It seems my prog can't find an augumentable path after matching 4 pairs of vertices. Could you help me?
program ural1099;
const
maxn=222;
var
g:array[1..maxn,1..maxn]of shortint;
{0:no path;1:path not in the augtree;-1:path in the augtree}
l:array[1..maxn,1..2]of byte;
{l[i,1]:the vertex before i on the augpath, if it's uncovered;
l[i,2]:the vertex before i on the augpath, if it's covered}
p:array[1..maxn]of byte;
{0 if it's uncovered, otherwise <i,p[i]> is a matched edge}
n,i,j,total:byte;
procedure exchange(i,j:integer);
{exchange matched and unmatched edges on the augpath}
begin
p[j]:=i;
while l[i,2]<>255 do begin
p[i]:=j;j:=l[i,2];
p[j]:=l[j,1];i:=p[j];
end;
p[i]:=j;
end;
function aug:boolean;
var
i,j,k{root of blossom},q,v:byte;
s:set of 1..maxn;{Vertices in the blossom}
more:boolean;{Whether to go on searching for augpath}
begin
aug:=true;
repeat
more:=false;
for i:=1 to n do
if l[i,2]>0 then{i is an outer vertex}
for j:=1 to n do
if (g[i,j]>0) and (p[i]<>j) then{an unmatched edge exists}
if (l[j,1]=0) and (l[j,2]=0) then{j isn't in the interlaced tree}
if p[j]=0 then begin{j is uncovered}
exchange(i,j);
exit;
end
else begin{j is covered}
g[i,j]:=-g[i,j];g[j,i]:=-g[j,i];
l[j,1]:=i;l[p[j],2]:=j;
g[j,p[j]]:=-g[j,p[j]];g[p[j],j]:=-g[p[j],j];
more:=true;
end
else if (l[j,1]=0) and (l[j,2]>0) then begin
{i and j are both outer vertices, build blossom}
more:=true;
g[i,j]:=-g[i,j];g[j,i]:=-g[j,i];
s:=[i];k:=i;v:=2;
while l[k,v]<>255 do begin
k:=l[k,v];s:=s+[k];v:=3-v;
end;
k:=j;v:=2;
while not (k in s) do begin
k:=l[k,v];v:=3-v;
end;
if l[i,1]=0 then begin{one blossom for i is enough}
l[i,1]:=j;q:=i;v:=2;
while q<>k do begin
l[l[q,v],v]:=q;q:=l[q,v];v:=3-v;
end;
end;
l[j,1]:=i;q:=j;v:=2;
while q<>k do begin
l[l[q,v],v]:=q;q:=l[q,v];v:=3-v;
end;
end;
until not more;
aug:=false;
end;
procedure match;
var
i,j,k:byte;
b:boolean;
begin
fillchar(p,sizeof(p),0);
repeat
i:=0;
repeat
inc(i);
if p[i]=0 then begin
fillchar(l,sizeof(l),0);
l[i,2]:=255;
b:=aug;
for j:=1 to n do
for k:=1 to n do
g[j,k]:=abs(g[j,k]);
end
else
b:=false;
until (i>n) or b;
if i<=n then inc(total);
until (i>n) or (total=n div 2);
end;
begin
fillchar(g,sizeof(g),0);
readln(n);
while not eof(input) do begin
readln(i,j);
g[i,j]:=1;g[j,i]:=1;
end;
total:=0;
match;
writeln(total*2);
for i:=1 to n do
if p[i]>0 then begin
writeln(i,' ',p[i]);
p[p[i]]:=0;
end;
end.