New Year congratulations
Time limit = 1 second(s)
Peter wants to congratulate his friends on the New Year day. Peter has N postcards and K envelopes, but some postcards don't fit in some envelopes (Peter knows which cards fit in which envelopes). Peter wants to congratulate as many friends as possible, but he doesn't know programming languages. Please help him: write the program that determines what envelopes and cards he should use and how.
Input: The first line of input contains three numbers N, K, C, separated by space. Then C pairs of integers follow, one pair per line. The A-th card may be put into the B-th envelope if and only if a pair (A, B) occurs in the input.
Output: The first line of ouput must contain X — the maximal number of card-envelope pairs. The next X lines must list the pairs, with pair (A, B) meaning that the A-th card must be put into the B-th envelope.
If there are many solutions, you should output one of them.
0 < N, K, C ≤ 1000 .
|
Input#1
2 2 3
1 1
1 2
2 1
|
Output#1
2
1 2
2 1
|
Program Mipt_010_Mpq;
Const Maxn=1000;
var
n,c,k,answer:integer;
sy:array[1..Maxn] of boolean;
cx,cy:array[1..Maxn] of integer;
g:array[1..Maxn,1..Maxn] of boolean;
procedure init;
var
i,x,y,c:integer;
begin
readln(n,k,c);
for i:=1 to c do
begin
readln(x,y);
g[x,y]:=true;
end;
end;
function Find(p:integer):boolean;
var
i:integer;
begin
for i:=1 to k do
if (Not sy[i]) and (g[p,i]) then
begin
sy[i]:=true;
if (cy[i]=0) or (Find(cy[i])) then
begin
cy[i]:=p;
cx[p]:=i;
exit(true);
end;
end;
exit(false);
end;
procedure Km;
var
i:integer;
begin
answer:=0;
fillchar(cx,sizeof(cx),0);
fillchar(cy,sizeof(cy),0);
for i:=1 to n do
begin
fillchar(sy,sizeof(sy),0);
if Find(i) then inc(answer);
end;
writeln(answer);
for i:=1 to n do
if cx[i]<>0 then
writeln(i,' ',cx[i]);
end;
begin
init;
Km;
end.