<PREV Problem:
NEXT>
Solved by 623 users: ...
UserDateAttemptTimeCMSC
abortmozga.ru22 aug 2009C++2200.07154 
abortmozga.ru22 aug 2009C++2100.07156 
abortmozga.ru22 aug 2009C++2000.06158 
vi00213 may 2008C++800.53159 
abortmozga.ru22 aug 2009C++1900.06160 
abortmozga.ru22 aug 2009C++1800.06164 
david_it2114 apr 2008C++6500.88170 
old103 aug 2006C++5300.34191 
old103 aug 2006C++5200.33194 
optimus01 sep 2009Ruby4102.22196 
old104 may 2006C++2900.33202 
AsukaNoKaze23 may 2006C++200.24205 
byjkper203 feb 2008C++100.08210 
Philip_PV01 aug 2008C400.08211 
old104 may 2006C++2800.08214 
Philip_PV01 aug 2008C300.07217 
var28 apr 2007C++100.32219 
avtoruxadze17 feb 2007C++200.08220 
Languages
C++
368
FPC
171
C
48
Kylix
29
Java
26
Ruby
1
Python
1
Perl
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 ≤ 1000, 0 ≤ C ≤ 12000.

Input#1
2 2 3
1 1
1 2
2 1

Output#1
2
1 2
2 1

Author:
Description by Eugene Barsky.
15 April 2004

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 18.208.202.194