<PREV Problem:
NEXT>
Solved by 617 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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 200ms

SW soft NIX
ID = 54.162.181.75