Solved by 623 users: ...
UserDateAttemptTimeCMSC
abortmozga.ru`22 aug 2009`C++2200.07154
abortmozga.ru`22 aug 2009`C++2100.07156
abortmozga.ru`22 aug 2009`C++2000.06158
vi002`13 may 2008`C++800.53159
abortmozga.ru`22 aug 2009`C++1900.06160
abortmozga.ru`22 aug 2009`C++1800.06164
david_it21`14 apr 2008`C++6500.88170
old1`03 aug 2006`C++5300.34191
old1`03 aug 2006`C++5200.33194
optimus`01 sep 2009`Ruby4102.22196
old1`04 may 2006`C++2900.33202
AsukaNoKaze`23 may 2006`C++200.24205
byjkper2`03 feb 2008`C++100.08210
Philip_PV`01 aug 2008`C400.08211
old1`04 may 2006`C++2800.08214
Philip_PV`01 aug 2008`C300.07217
var`28 apr 2007`C++100.32219
avtoruxadze`17 feb 2007`C++200.08220
 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

 © acm.mipt DevGroupThe page was generated in 220ms