MATCH1 - Cặp ghép không trọng số
Tác giả: flashmt
Ngôn ngữ: Pascal
var n,m,x,y,re,nq,i:longint;
c,f:array[1..111,1..111] of longint;
a,b,d,q:array[1..111] of longint;
function find(var u:longint):boolean;
var i:longint;
begin
fillchar(d,sizeof(d),0);
nq:=0;
for i:=1 to m do
if a[i]=0 then
begin
inc(nq);
q[nq]:=i;
end;
i:=1;
while i<=nq do
begin
x:=q[i]; inc(i);
for y:=1 to n do
if (d[y]=0) and (c[x][y]=1) then
begin
d[y]:=x;
if b[y]=0 then
begin
u:=y; exit(true);
end;
inc(nq);
q[nq]:=b[y];
end;
end;
find:=false;
end;
procedure incflow(y:longint);
var x,t:longint;
begin
while y>0 do
begin
x:=d[y]; t:=y; y:=a[x];
b[t]:=x; a[x]:=t;
end;
end;
begin
read(m,n);
while not eof do
begin
read(x);
if x<=0 then break;
read(y);
c[x][y]:=1;
end;
while find(i) do incflow(i);
for i:=1 to m do
if a[i]>0 then inc(re);
writeln(re);
for i:=1 to m do
if a[i]>0 then writeln(i,' ',a[i]);
end.