Online MIPT programming contest | РУССКИЙ |
<PREV Problem: | NEXT> |
< |
---|
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#12 2 3 1 1 1 2 2 1 |
Output#12 1 2 2 1 |
Author:
Description by Eugene Barsky.
15 April 2004
© acm.mipt DevGroup The page was generated in 170ms |