/*
Definitii:
Un graf se numeste bipartit daca exista o colorare a nodurilor in culorile 0 si 1
astfel incat orice muchie sa aiba capete de culori diferite.

6 3 -> 6 noduri, 3 muchii
1 2
3 4
5 6

-> Exista 2 colorari valide: {1:0, 2:1, 3:0, 4:1, 5:0, 6:1} si 
                             {1:1, 2:0, 3:0, 4:1, 5:0, 6:1} si
							 {1:1, 2:0, 3:1, 4:0, 5:0, 6:1} si
							 {1:0, 2:1, 3:1, 4:0, 5:1, 6:0} si altele

Lema! Daca graful este conex, avem 2 colorari echivalente (una este cealalta inversata)

Lema! Intr-un graf bipartit, nu exista cicluri de lungime impara.
Inversa lemei! Daca un graf nu are cicluri de lungime impara, atunci este bipartit.

Cum verificam daca un graf este bipartit?

Algoritm!
1. Creeam un vector/map de culoare, in care initial fiecare nod are culoarea -1.
2. Pornind de la orice nod din graf (in general se alege 1), ii atribuim culoarea 0.
3. Vecinilor le atribuim culoarea 1.
4. Recursiv, vecinilor vecinilor le atribuim culoarea 0, si asa mai departe.
5. Practic, incepem un DFS de la nodul 1 in care punem culoarea diferita 
   de culoarea nodului din care venim.
6. Daca incercam vreodata sa coloram cu alta culoare un nod deja colorat, 
   inseamna ca graful nu este bipartit.
7. Daca am colorat tot graful fara sa ne lovim de cazul de la 6,
   inseamna ca graful este bipartit.

8. Se vor nota cele 2 componente bipartite L, R
   si se vor construi astfel:
	```cpp
	vector <int> L, R;
	for( int i = 1; i <= n; i++ )
		if( culoare[i] == 0 ) L.push_back(i);
		else R.push_back(i);
	```

Definitii:
Cuplaj - o selectie de muchii din graful bipartit, astfel incat
		 nu exista 2 muchii care sa aiba un nod in comun.

Pe Graful din Exemplu, un cuplaj posibil este:
{ 1 - 5 }
sau { 2 - 5, 3 - 4 } - maximal
sau { 1 - 5, 3 - 4, 2 - 6 } - maxim

Cuplaj maximal - un cuplaj care nu poate fi extins cu nicio muchie.
Cuplaj maxim - este cel mai mare cuplaj ca numar de muchii
Cuplaj perfect - un cuplaj in care fiecare nod din L este cuplat cu un nod din R si vice versa
			   - se intampla in cazul in care |L| = |R| si cuplajul maxim = |L| = |R|

Strategie de augmentare:
Pentru un cuplaj C dat, se cauta un drum alternant de la un nod din L la un nod din R.
Vom gasi un drum alternant D = l[0], r[0], l[1], r[1], ..., l[k], r[k]
Cu urmatoarele proprietati:
l[0] si r[k] nu sunt cuplati
muchiile (l[0] - r[0]) (l[1] - r[1]) ... (l[k] - r[k]) nu sunt in cuplajul C
muchiile (r[0] - l[1]) (r[1] - l[2]) ... (r[k-1] - l[k]) sunt in cuplajul C

Atunci, putem crea un cuplaj nou C' dupa regula:
muchia m este in C' daca m este in drumul alternant de la l[i] la r[i]
				 sau daca m este in C si nu este in drumul alternant de la r[i] la l[i+1]
Fiindca drumul D are lungime = 2k, C' are cu o muchie mai mult decat C.

```cpp
pereche_stanga[x - nod din dreapta] = y - nodul din stanga
inseamna ca x si y sunt cuplati
pereche_stanga[x] = 0 inseamna ca x nu este cuplat

Cuplaj C;

bool cauta_drum_alternant(int nod -> din stanga) {
	for(auto vec : g[nod]) {
		if (vizitat[vec]) continue;
		if (pereche_stanga[vec] == 0) { // daca nu are pereche, am gasit final de drum alternant
			// Am gasit drum alternant care se termina cu muchia (nod - vec)
			C.insert({nod, vec});
			return true;
		}
		else { // daca are pereche, incerc in continuare sa caut un drum alternant de la pereche_stanga[vec]
			vizitat[vec] = true;
			if (cauta_drum_alternant(pereche_stanga[vec])) {
				// daca gasesc drumul, muchia {nod, vec} este in drumul alternant si trebuie adaugata
				C.insert({nod, vec});
				C.erase({pereche_stanga[vec], vec}); // muchia aceasta era pe o pozitie impara in drum, deci trebuie scoasa
				return true;
			}
		}
	}

	return false;
}
*/

#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_stanga[nmax];
int vizitat[nmax];
int imperecheat[nmax];

// Nu mai folosesc vreo structura de Cuplaj numita C
// Ci doar schimb vectorul de perechi pereche_stanga
// atunci cand se adauga / scoate o muchie noua
bool cauta_drum_alternant(int nod) {
	random_shuffle(ltor[nod].begin(), ltor[nod].end());
	for(auto vec : ltor[nod]) {
		if (vizitat[vec]) continue;
		vizitat[vec] = true;
		if (pereche_stanga[vec] == 0) {
			pereche_stanga[vec] = nod; // C.insert({nod, vec})
			imperecheat[nod] = vec;
			return true;
		}
		else {
			if (cauta_drum_alternant(pereche_stanga[vec])) {
				// pereche_stanga[vec] = 0; // C.erase({pereche_stanga[vec], vec})
				// imperecheat[pereche_stanga[vec]] = 0;
				pereche_stanga[vec] = nod; // C.insert({nod, vec})
				imperecheat[nod] = vec;
				return true;
			}
		}
	}

	return false;
}

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

	bool ok = true;
	while(ok) {
		ok = false;
		memset(vizitat, 0, sizeof(vizitat)); // resetez vectorul de vizitat

		for(int i = 1; i <= n; i++) {
			if ( imperecheat[i] == 0 && cauta_drum_alternant(i) ) {
				ok = true;
				// break;
			}
		}

		/* for(int i = 1; i <= m; i++) {
			cerr << pereche_stanga[i] << ' ';
		}
		cerr << endl; */
	}

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

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