#include <cstdio>
#include <cstdlib>
#define DIM 20005
struct muchie
{
int x, capflux;
muchie *next;
};
muchie *G[DIM];
int n, m , nr_cuplaj, nrM, tata[DIM], cuplaj;
void addMuchie(int i, int j, int cf)
{
muchie *t = new muchie;
t -> x = j;
t -> capflux = cf;
t -> next = G[i];
G[i] = t;
}
void Read()
{
FILE *f = fopen("cuplaj.in", "r");
fscanf(f, "%d%d%d", &n, &m, &nrM);
for (int i = 1, x, y; i <= nrM; ++i)
{
fscanf(f, "%d%d", &x, &y);
addMuchie(x, y + n, 1);
addMuchie(y + n, x, 0);
}
for (int i = 1; i <= n; ++i)
addMuchie(0, i, 1),
addMuchie(i, 0, 0);
for (int i = n + 1; i <= n + m; ++i)
addMuchie(i, n + m + 1, 1),
addMuchie(n + m + 1, i, 0);
fclose(f);
}
int BFS(int s, int d)
{
int coada[DIM], st, dr, k, i;
st = dr = 1;
for (i = 0; i <= n + m + 1; ++i)
tata[i] = -2;
coada[1]=s, tata[s] = -1;
while (st <= dr)
{
k = coada[st++];
for (muchie *t = G[k]; t; t = t->next)
{
i = t -> x;
if (tata[i] == -2 && t->capflux)
coada[++dr] = i, tata[i] = k;
}
if (k == d)
return 1;
}
return 0;
}
muchie * adresa_muchie (int i, int j)
{
for (muchie *p = G[i]; p ; p = p -> next)
if (p -> x == j)
return p;
printf ("baaaaaa\n");
return NULL;
}
void e_k()
{
int k, i, dcur, j;
muchie *p;
while (BFS(0, n+m+1))
{
for (j = n + 1; j <= n+m; ++j)
{
p = adresa_muchie(j, n+m+1);
if (p->capflux == 0 || tata[j] == -2)
continue;
k = n+m+1;
tata[k] = j;
dcur = 4;
while (tata[k] != -1)
{
p = adresa_muchie(tata[k], k);
if (p->capflux < dcur)
dcur = p->capflux;
k = tata[k];
}
cuplaj += dcur;
k = n+m+1;
while (tata[k] != -1)
{
p = adresa_muchie(tata[k], k);
p->capflux -= dcur;
p = adresa_muchie(k, tata[k]);
p->capflux += dcur;
k = tata[k];
}
}
}
}
int main()
{
Read();
e_k();
FILE *f = fopen("cuplaj.out", "w");
fprintf (f, "%d\n", cuplaj);
for (int i = 1, gasit = 0; i <= n; ++i)
{
gasit = 0;
for(muchie *t = G[i]; t && !gasit; t = t -> next)
if (t->capflux == 0 && t->x > n)
fprintf (f, "%d %d\n", i, t->x), gasit = 1;
}
fclose(f);
return 0;
}