program matchs; const MaxN=100; var G:array[1..MaxN,1..MaxN] of boolean; N,M:longint; A,B:array[1..MaxN] of word; mc:word; procedure ReadData; var i,j:word; k:longint; begin readln(N,M); for i:=1 to N do for j:=1 to N do G[i,j]:=false; for k:=1 to M do begin readln(i,j); G[i,j]:=true; end; end; procedure EvalMatchs; var St:array[0..MaxN] of longint; Stc:longint; BT:array[1..MaxN] of word; marked:array[1..MaxN] of boolean; fin:boolean; i,j,w,r:word; procedure Alternate; var k,l:word; begin fin:=true; inc(mc); k:=j; l:=i; repeat B[k]:=l; w:=A[l]; A[l]:=k; k:=w; l:=BT[l]; until l=0; end; begin mc:=0; for i:=1 to N do begin A[i]:=0; B[i]:=0 end; for r:=1 to N do begin BT[r]:=0; fin:=false; Stc:=1; St[0]:=r; for i:=1 to N do marked[i]:=false; while (Stc>0) and (not fin) do begin dec(Stc); i:=St[Stc]; for j:=1 to N do if (A[i]<>j) and G[i,j] and (not fin) and (not marked[j]) then if B[j]=0 then Alternate else begin w:=B[j]; marked[j]:=true; BT[w]:=i; St[Stc]:=w; inc(Stc); end; end; end; end; procedure WriteResult; var i:word; begin writeln('mathcs=',mc); for i:=1 to N do if A[i]>0 then writeln(i,' ',A[i]); end; begin ReadData; EvalMatchs; WriteResult; end.