/*
Definitii:
Graf bipartit: un graf in care putem colora fiecare nod cu 0 sau 1
			   astfel incat orice muchie sa aiba capetele de culori diferite.
			   
Verificare daca un graf este bipartit:
Incepem sa coloram de la un nod cu culoarea 0
Toti vecinii lui vor avea culoarea 1
Toti vecnii vecinilor lui vor avea culoarea 0
....
Daca un nod initial colorat cu 0 are un vecin colorat cu 0, atunci graful nu este bipartit.
Similar daca avem o muchie 1 - 1, atunci graful nu este bipartit.

Daca nu avem nicio eroare la colorare, putem imparti graful in 2 parti, fie ele L si R
L = nodurile colorate cu 0
R = nodurile colorate cu 1
Orice muchie are un capat in L si un capat in R

Lema 1. Daca un graf este bipartit si conex, atunci exista o singura impartire a.i. 
        nodul 1 sa fie in L

Lema 2. Daca un graf este bipartit -> acest graf nu are cicluri de lungime impara
Si inversa Lemei 2. Daca un graf nu are cicluri de lungime impara -> este bipartit

Cuplaj : o selectie de muchii dintr-un graf bipartit a.i. oricare doua muchii
		 din cuplaj sa nu aiba niciun nod in comun
		 (a - b) si (c - d) cu a, c in L si b, d in R
		 -> a != c si b != d

Cuplaj:
maximal - daca nu exista o muchie in graf care i se poate adauga
maxim - daca nu exista un cuplaj mai mare in graf (unde mai mare = cu mai multe muchii selectate)
perfect - daca fiecare nod din L are o muchie in cuplaj, la fel si pentru R
		  |perfect| = |L| = |R|

Evident, orice cuplaj perfect este maxim.
Ca sa verificam daca un graf bipartit are un cuplaj perfect, doar verificam
marimea cuplajului maxim!

IMPORTANT! Nu orice cuplaj maximal este si maxim!

Principala metoda de a gasi un cuplaj maxim,
este de a porni de la un cuplaj de marime k si cu ajutorul lui
a creea un cuplaj de marime k + 1!

Problema! Cum adica gasim un cuplaj de marime k + 1? Inseamna 
ca acel cuplaj de marime k nu este maximal? NU

Noi nu avem nevoie de un cuplaj non-maximal, pe motiv ca 
noi nu adaugam o singura muchie in pasul de extindere - "augmentare"

Noi putem augmenta un cuplaj si "inlocuind" intr-un anumit mod muchiile
care deja se aflau in cuplaj!

Daca sa zicem ca avem un cuplaj C = {(L1 - R2)}
Dar setul total de muchii mai contine si muchiile (L1 - R1) si (L2 - R2)
Atunci putem sa inlocuim muchia (L1 - R2) cu (L1 - R1) si (L2 - R2)
rezultand un cuplaj de marime 2: C' = {(L1 - R1), (L2 - R2)}

Motivul pentru care putem face asta este pentru ca exista un drum "alternant"

Drumul alternant! Este o serie de noduri si muchii a.i.
1. Nodurile nu se repeta
2. Incepe cu un nod din L si se termina cu un nod din R
3. Daca drumul este L0, R0, L1, R1, L2, R2, ..., Lk, Rk
   atunci muchiile (L0 - R0), (L1 - R1), ..., (Lk - Rk) nu sunt luate in cuplajul initial C
   iar muchiile (R0 - L1), (R1 - L2), ..., (R(k - 1) - Lk) sunt luate in cuplajul initial C

Daca in cuplajul initial adaugam toate muchiile de la Li la Ri
si scoatem toate muchiile de la Ri la L(i + 1), 
atunci tocmai am scos k - 1 muchii si am adaugat k muchii inapoi

Per total, avem un profit de +1 muchie luata in cuplaj!

O intrebare ramane: Cum gasim un astfel de alternating/augmenting path?
Raspunsul: DFS!

Sa presupunem ca avem grija si retinem intr-un vector numit
"pereche" pentru fiecare nod din R, nodul din L cu care este cuplat sau 0
daca inca nu are pe nimeni
cuplat[x -> nod din L] = 0 daca nu este cuplat cu cineva din R, 1 daca da
pereche[x -> nod din R] = y -> nod din L daca (x - y) este in cuplaj, 0 altfel

Cuplaj C;
 /----> returneaza true daca a gasit un drum alternant pornind de la nod
bool cauta_drum_alternant(int nod : nod din L) {
	for(auto vec : g[nod]) {
		if(vizitat[vec]) continue;
		vizitat[vec] = true; 

		if(pereche[vec] == 0) {
			C.insert({nod, vec}); // presupun ca asta updateaza si pereche si cuplat
			return true;
		}
		
		if(cauta_drum_alternant(pereche[vec])) {
			C.erase({pereche[vec], vec})
			C.insert({nod, vec});
			return true;
		}
	}

	return false;
}

Voi tot apela functia cauta_drum_alternant pentru fiecare nod din L
pana nu mai gasesc nimic (avand grija sa resetez vectorul de vizitare
de fiecare data cand gasesc ceva)
*/

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("cuplaj.in");
ofstream out("cuplaj.out");
#define cin in
#define cout out
#endif // LOCAL

const int nmax = 1e4 + 5;
vector<int> ltor[nmax];
int pereche[nmax], cuplat[nmax];
bool vizitat[nmax];

bool cauta_drum_alternant(int nod) {
	for(auto vec : ltor[nod]) {
		if(vizitat[vec]) continue;
		vizitat[vec] = true;

		if(pereche[vec] == 0) {
			// C.insert({nod, vec});
			cuplat[nod] = vec;
			pereche[vec] = nod;
			return true;
		}

		if(cauta_drum_alternant(pereche[vec])) {
			// cuplat[pereche[vec]] = 0; // doar ca deja s-a recuplat in 
			// apelarea recursiva precedenta
			cuplat[nod] = vec;
			pereche[vec] = nod;
			return true;
		}
	}

	return false;
}

int main() {
	int n, m, e; cin >> n >> m >> e;
	for(int i = 1; i <= e; i++) {
		int a, b; cin >> a >> b;
		ltor[a].push_back(b);
	}

	bool ok = true;
	while(ok) {
		ok = false;
		// resetam vectorul de vizitat
		memset(vizitat, 0, sizeof(vizitat)); // O(n) pentru fiecare drum alternant gasit

		for(int i = 1; i <= n; i++) {
			if(cuplat[i] == 0 && cauta_drum_alternant(i)) {
				ok = true;
				// Optimizarea 1: scoatem acest 
				// break;
			}
		}
	}

	vector<pair<int, int>> cuplaj;
	for(int i = 1; i <= m; i++) {
		if(pereche[i] != 0) {
			cuplaj.push_back({pereche[i], i});
		}
	}

	cout << cuplaj.size() << '\n';
	for(auto muchie : cuplaj) {
		cout << muchie.first << ' ' << muchie.second << '\n';
	}
}