#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define MAX_SIZE 1024

using namespace std;

int L, R, M, N, x, y;
vector<int> adjList[MAX_SIZE];

// Matrice ce retine capacitatea maxima pentru fiecare muchie in parte

int C[MAX_SIZE + 1][MAX_SIZE + 1];

// Matrice ce retine fluxul curent pentru fiecare muchie in parte

int F[MAX_SIZE + 1][MAX_SIZE + 1];


vector<pair<int, int>> drumuri = vector<pair<int, int>>(); 

int main() {

    ifstream fin("cuplaj.in");
    ofstream fout("cuplaj.out");

    // Se citesc cardinanul multimii L, resp cardinalul multimii R si numarul de muchii
    fin >> L >> R >> M; 

    // Numarul de noduri (cu tot cu sursa si destinatia care vor fi adaugate) va fi egal cu L + R + 2

    N = L + R + 2;

    // Se citesc muchiile
    for(int i = 0; i < M; ++i) {

        // x face parte din prima componenta (L), iar y din cea de-a doua componenta (R)

        fin >> x >> y;

        // Pentru ca nodurile din cea de-a doua multime sunt numerotate incepand tot de la 1, trebuie sa adunam la ele L

        y = y + L;


        printf("Se adauga muchie intre %d si %d\n", x, y);

        adjList[x].push_back(y);

        // Trebuie sa legam sursa (nodul 0) de toate nodurile din L printr-o muchie de capacitate 1 

        adjList[0].push_back(x);
        C[0][x] = 1;


        // Trebuie sa adaugam si muchia inversa (graf rezidual)

        adjList[x].push_back(0);

        // Trebuie sa legam fiecare nod din R de destinatie (L + R + 1) printr-o muchie de capacitate 1
        
        adjList[y].push_back(L+R+1);

        C[y][L+R+1] = 1;

        // Trebuie sa adaugam si muchia inversa (graf rezidual)

        adjList[L+R+1].push_back(y);

        // Construim direct graful rezidual, adaugam si muchia (y,x) in lista de adiacenta
        
        adjList[y].push_back(x);

        // Capacitatea pe (x, y) este 1. 
        C[x][y] = 1;
    
    }

    // Trebuie sa adaugam un nod sursa pe care sa il legam de toate nodurile din L (pt ca nodurile din L incep de la 1, sursa va fi 0) 
    int S = 0;
    // Trebuie sa adaugam un nod destinatie pe care sa il legam de toate nodurile din R (cum nodurile din L si R sunt in numar de L + R si sunt indexate de la 1, trebuie sa punem destinatia pe pozitia L + R + 1)  
    int D = L + R + 1;





    //cout << "Destinatia este " << D << "\n";

    // Daca am gasit sau nu un path de ameliorare, ne ajuta sa stim cand ne oprin din a face BFS pe graful rezidual 

    bool augumentationPathFound = false;

    // Coada ce va fi folosita pentru parcurgerea BF

    queue<int> q;

    // Vector ce va retine daca un nod este vizitat sau nu in cadrul parcurgerii

    vector<bool> visited;

    // Vectorul de tati al arborelui generat de BFS 

    vector<int> parent; 

    // Daca am ajuns la nodul destinatie in BFS 

    bool destinationReched; 

    // Variabila ce va retine la final flow-ul maxim si va reprezenta suma flow-urilor de pe toate drumurile de ameliorare gasite

    int totalFlow = 0;

    do {

        // Pentru fiecare iteratie a BFS-ului trebuie sa resetam coada, vectorul visited, vectorul de tati si destinationReached

        q = queue<int>();
        visited = vector<bool>(N+1, false);
        parent = vector<int>(N+1, -1);
        destinationReched = false;

        // Incepem prin a introduce in coada nodul de start

        q.push(S);

        // Cat timp coada nu este vida

        while(!q.empty() && !destinationReched) {

            // Scoatem cel mai vechi nod din coada si il marcam ca si vizitat

            auto currentNode = q.front();
            q.pop();
            visited[currentNode] = true;

            // Trecem prin fiecare dintre nodurile vecine cu nodul curent

            for(int j = 0; j < adjList[currentNode].size(); j++) {
                auto currentNeighbor = adjList[currentNode][j];

                // Daca vecinul nu a fost inca vizitat si catre el capacitatea reziduala este mai mare decat 0 (capacitate - flux), atunci adaugam nodul in coada 
                
                if(!visited[currentNeighbor] && C[currentNode][currentNeighbor] - F[currentNode][currentNeighbor] > 0) {
                    q.push(currentNeighbor);

                    // Marcam si nodul vecin ca fiind vizitat 
                    visited[currentNeighbor] = true;

                    // Actualizam parintele nodului vecin (care este nodul curent)

                    parent[currentNeighbor] = currentNode;

                    // Daca am ajuns cumva la nodul destinatie, atunci oprim BFS-ul

                    if(currentNeighbor == D) {
                        destinationReched = true;
                        break;
                    }
                }
            }
        }

        if(destinationReched) {
            // cout << "S-a gasit un path de ameliorare vectorul de tati este: ";
            // for(auto x: parent) {
            //     cout << x << " ";
            // }


            //cout << " , iar muchiile ce compun path-ul sunt: ";
            // Daca am gasit un drum de ameliorare, atunci trebuie sa il reconstruim din vectorul de tati si sa actualizam fluxul muchiilor ce fac parte din acel drum


            int cNode = D;
            int pNode = D;
            int bottleneck = -1; 



            bool edgeFound = false;
            pair<int, int> cPair = pair<int, int>();

            while(true) {
                if(pNode == -1) {
                    break;
                }

                if(pNode != -1 && pNode != cNode) {


                    // Daca parent node-ul este egal cu 0, inseamna ca cNode (nodul curent) face parte din multimea L.

                    cout << "(" << pNode << " " << cNode << ") ";

                    // if(pNode == 0) {
                    //     cPair.first = cNode;
                    // }


                    // // Daca curent node-ul este egal cu destinatia (L+R+1), atunci inseamna ca pNode (parent node-ul) face parte din multimea R

                    // if(cNode == L + R + 1) {
                    //     cPair.second = pNode - L;
                    // } 
                    
                    if(cNode != L + R + 1 && !edgeFound) {
                        cPair.first = pNode;
                        cPair.second = cNode - L;
                        edgeFound = true;
                    }

                    if(bottleneck == -1 || C[pNode][cNode] - F[pNode][cNode] < bottleneck) {
                        bottleneck = C[pNode][cNode] - F[pNode][cNode];
                    }
                }

                cNode = pNode;

                pNode = parent[pNode];
            }

            printf("[%d %d] ", cPair.first, cPair.second);

            cout << "Pt path-ul de mai sus fluxul maxim pe care il putem adauga este egal cu " << bottleneck << "\n";

            cNode = D;
            pNode = D;

            while(true) {
                if(pNode == -1) {
                    break;
                }

                if(pNode != -1 && pNode != cNode) {
                    // Scadem bottleneck-ul din muchia din graful initial si adaugam la muchia inversa bottleneck-ul cu semn schimbat
                    F[pNode][cNode] += bottleneck;
                    F[cNode][pNode] -= bottleneck;       
                }

                cNode = pNode;

                pNode = parent[pNode];
            }

            totalFlow += bottleneck;

            cout << "\n";
            augumentationPathFound = true;
        } else {
            augumentationPathFound = false;
        }

    } while(augumentationPathFound);


    cout << "Flow-ul maxim este " << totalFlow;  

    fout << totalFlow;

    return 0;
}