/*
	Cuplaj maxim in graf bipartit   https://www.infoarena.ro/problema/cuplaj
		Se dă un graf neorientat bipartit G = (V = (L, R), E). Un cuplaj în G este o submulţime de muchii M astfel încât pentru toate vârfurile v din V, există cel mult o muchie în M 
	incidentă în v. Un cuplaj maxim este un cuplaj de cardinalitate maximă.

	Cerinţa
		Dându-se un graf neorientat bipartit G să se determine un cuplaj maxim.

	Date de intrare
		Fişierul de intrare cuplaj.in conţine pe prima linie trei numere naturale N, M şi E, unde N reprezintă cardinalul mulţimii L iar M cardinalul mulţimii R. Pe următoarele E 
	linii se vor afla câte două numere naturale, separate între ele printr-un spaţiu, u şi v, cu semnificaţia că există muchie de la nodul u din L la nodul v din R.

	Date de ieşire
		În fişierul de ieşire cuplaj.out veţi afişa pe prima linie un singur număr reprezentând cuplajul maxim. Pe fiecare din următoarele linii veţi afişa câte două numere x şi y, 
	separate între ele prin spaţiu, cu semnificaţia că nodul x din L a fost cuplat cu nodul y din R.
*/

#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std; 

int nrNoduri, destinatie;

vector<vector<int>> listaAdiacenta; 

struct muchie
{
	int nodIesire, nodIntrare, capacitate, pozitie;
};
vector<muchie> muchii; 

int cardinalL, cardinalR, nrMuchii;

void citire()
{
	ifstream fin("cuplaj.in"); 

	fin >> cardinalL >> cardinalR >> nrMuchii; 

	nrNoduri = cardinalL + cardinalR + 2; 
	destinatie = nrNoduri - 1;

	listaAdiacenta.resize(nrNoduri + 1); 

	//citire muchii
	int nodIesire, nodIntrare; 
	for (int i = 1; i <= nrMuchii; i++)
	{
		fin >> nodIesire >> nodIntrare; 
		muchii.push_back({nodIesire, nodIntrare + cardinalL, 1, 2 * i - 1});
		muchii.push_back({nodIntrare + cardinalL, nodIesire, 0,2 * i - 2 });

		listaAdiacenta[nodIntrare + cardinalL].push_back(2 * i - 1); 
		listaAdiacenta[nodIesire].push_back(2 * i - 2); 
	}

	int dimMuchii = int(muchii.size()); 
	
	for (int i = 1; i <= cardinalL; i++)
	{
		dimMuchii += 2; 

		muchii.push_back({ 0, i, 1, dimMuchii - 1 }); 
		listaAdiacenta[i].push_back(dimMuchii - 1);

		muchii.push_back({ i, 0, 0, dimMuchii - 2});
		listaAdiacenta[0].push_back(dimMuchii - 2);

	}

	for (int i = cardinalL + 1; i < nrNoduri - 1; i++)
	{
		dimMuchii += 2;

		muchii.push_back({ i, destinatie, 1, dimMuchii - 1 }); 
		listaAdiacenta[destinatie].push_back(dimMuchii - 1); 

		muchii.push_back({destinatie, i, 0, dimMuchii - 2});
		listaAdiacenta[i].push_back(dimMuchii - 2); 
	}

	fin.close(); 
}

vector<bool> vizitat;
vector <int> tata;

//in cadrul parcurgerii BFS caut lanturi de la nodul de inceput (nodul 1) la nodul final (nodul nrNoduri) in care fiecare muchie sa aiba capacitatea reziduala mai mica decat capacitatea initiala
bool BFS()
{
	queue<int> vecini;

	tata.clear();
	tata.resize(nrNoduri + 1, 0);

	vizitat.clear();
	vizitat.resize(nrNoduri + 1, false);

	vecini.push(0);
	vizitat[0] = true;
	while (!vecini.empty())
	{
		int nodCurent = vecini.front();
		vecini.pop();

		if (nodCurent == destinatie) //am ajuns la nodul de sfasit, asadar am gasit un lant care respecta criteriile impuse, deci ies din structura repetitiva
			continue;

		for (int vecin : listaAdiacenta[nodCurent])
		{
			muchie muchie = muchii[vecin]; 
			if (!vizitat[muchie.nodIntrare] && muchie.capacitate > 0)
			{
				tata[muchie.nodIntrare] = vecin;
				vecini.push(muchie.nodIntrare);
				vizitat[muchie.nodIntrare] = true;
			}
		}
	}

	return vizitat[destinatie];
}

int fluxMaxim = 0; 

//algoritmul edmonds-karp: 
void EdmondsKarp()
{

	//pentru gasirea drumurilor de ameliorare (drum de la sursa la destinatie, in care fiecare muchie de pe drum sa aiba fluxul asociat pana in acest moment strict mai mic decat capacitatea sa) folosesc parcurgere BFS
	//cat timp exista astfel de drumuri de ameliorare, le parcurg, adaugand flux
	while (BFS())
	{
		//penrtu fiecare drum de ameliorare gasit, caut bottleneck-ul (valoarea minima cu care poate fi marit fluxul asociat fiecarei muchii care se afla pe drumul gasit) si updatez capacitatile reziduale 
		for (auto vecin : listaAdiacenta[destinatie])
		{
			muchie muchie = muchii[vecin]; 
			if (vizitat[muchie.nodIntrare] && muchii[muchie.pozitie].capacitate != 0)
			{
				int nodCrt = destinatie; 
				tata[destinatie] = muchie.pozitie; 
				int fluxCrt = INT_MAX; 

				while (nodCrt != 0)
				{
					if (fluxCrt > muchii[tata[nodCrt]].capacitate)
						fluxCrt = muchii[tata[nodCrt]].capacitate; 

					nodCrt = muchii[tata[nodCrt]].nodIesire; 
				}


				nodCrt = destinatie;

				while (nodCrt != 0)
				{
					muchii[tata[nodCrt]].capacitate -= fluxCrt; 
					muchii[muchii[tata[nodCrt]].pozitie].capacitate += fluxCrt; 

					nodCrt = muchii[tata[nodCrt]].nodIesire; 
				}

				fluxMaxim += fluxCrt; 
			}
		}
	}

}

void afisare()
{
	ofstream fout("cuplaj.out");

	fout << fluxMaxim << "\n"; 

	for (auto muchie : muchii)
	{
		if (muchie.capacitate == 0 && muchie.nodIesire != 0 && muchie.nodIntrare != destinatie && muchie.nodIesire < muchie.nodIntrare)
		{
			fout << muchie.nodIesire << " " << muchie.nodIntrare - cardinalL << "\n"; 
		}
	}

	fout.close();
}


//Pentru rezolvarea problemei voi trata muchiile date ca fiind arce orientate de la multima stanga la multimea deaprta, cu capacitatea 1
//De asemenea, voiadauga doua noduri noi: nodul sursa si nodul destinatie, sursa se va uni de toare nodurile din multimea stanga printr-un arc al carui capacitate va fi de o unitate, iar toate nodruile din multimea dreapta se vor uni de destinatie prin cate un arc al carui capacitate va fi tot 1
//Folosind algoritmul  pentru determinarea fluxului maxim vom afla care este cuplajul maxim in graful dat
int main()
{
	citire(); 
	EdmondsKarp();
	afisare(); 
}