//Copyright: Costin Banu
/***********************************************************************************************
algoritmul lui HOPCROFT - KARP pt. determinarea unui cuplaj maxim cu submultimi ST si DR.
complexitate O(E*sqrt(N+M))

Cuplajul se realizeaza dupa urmatoarea regula:
   - pt. fiecare nod u nevizitat, consideram toate nodurile v adiacente cu el
       (i.e. in graful original, exista muchia (u,v))
   - pt. fiecare astfel de nod v, il adaugam la jumatatea dreapta, daca nu exista, si realizam
       cuplajul intre u si v, punand u in jumatatea stanga.
   - se incearca repetarea procesului pt. fiecare nod v adaugat astfel in jumatatea dreapta si
       toate nodurile adiacente cu el (evident, mai putin u), printr-o parcurgere tip DFS.

***********************************************************************************************/

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> g[10002];
bool viz[10002];
int N, M, E, l[10002], r[10002];

int cup(int u) {
   if (viz[u])  return 0;
   viz[u] = 1;
   ///toate v-urile adiacente cu u se adauga in dreapta, daca se poate
   for (vector <int>::iterator v = g[u].begin(); v != g[u].end(); v++)
       if (!r[*v]) {
           l[u] = *v;
           r[*v] = u;
           return 1;
       }
   ///se incearca procedeul pt. toate nodurile adiacente cu v-urile adaugate in dreapta
   for (vector <int>::iterator v = g[u].begin(); v != g[u].end(); v++)
       if (cup(r[*v])) {
           l[u] = *v;
           r[*v] = u;
           return 1;
       }
   return 0;
}

int main() {
   FILE *in = fopen("cuplaj.in", "r"), *out = fopen("cuplaj.out", "w");
   if (in && out) {
       fscanf(in, "%d %d %d\n", &N, &M, &E);
       for (int i = 0; i < E; i++) {
           int x, y;
           fscanf(in, "%d %d\n", &x, &y);
           g[x].push_back(y);
       }
       bool cont = 1;
       ///se incearca adaugarea la cuplaj a tuturor nodurilor cu procedeul de mai sus
       while ( cont ) {
           cont = 0;
           memset(viz, 0, sizeof(viz));
           for(int i = 1; i <= N; i++)
               if ( !l[i] && cup(i) ) cont = 1;
       }
       int cuplaj = 0;
       ///numaram cate noduri exista in cuplaj
       for(int i = 1; i <= N; i++)
           if ( l[i] ) cuplaj++;
       fprintf(out, "%d\n", cuplaj);
       ///afisam cuplajul ( muchia (i,l[i]) este evident identica cu (r[i],i) )
       for(int i = 1; i <= N; i++)
           if ( l[i] )
               fprintf(out, "%d %d\n", i, l[i]);
   }
   return 0;
}