#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// find_maximum_matching nájde jedno maximálne párovanie v danom bipartitnom grafe
// "A", "B" sú veľkosti ľavej a pravej partície ("počet chlapcov a dievčat")
// "edge_list" je zoznam dvojíc ("ktoré dvojice sú ochotné spolu tancovať")
// chlapcov aj dievčatá číslujeme od 0

vector< pair<int,int> >
find_maximum_matching(
        int A,
        int B,
        const vector< pair<int,int> > &edge_list)
{

    // pre každé dievča si zapamätáme hrany do 'jej' chlapcov

    vector< vector<int> > BA;
    BA.resize(B);
    for (const auto &e : edge_list) BA[ e.second ].push_back( e.first );

    // pre každého chlapca si budeme updatovať jeho aktuálnu partnerku
    // hodnota -1 znamená, že momentálne žiadnu nemá
    
    vector<int> match(A,-1);

    // na začiatku akoby máme všetkých chlapcov a žiadne dievčatá
    // postupne po jednom pridávame dievčatá
    // z pridaného dievčaťa vždy pustíme BFS ktorým hľadáme zlepšujúcu cestu

    for (int b=0; b<B; ++b) {

        // pribudlo dievča číslo b, ideme zistiť, či vieme zlepšiť riešenie

        // pre každého chlapca si pamätáme, či už bol počas BFS navštívený
        // from[a] == -1 : ešte navštívený nebol
        // from[a] == a  : bol navštívený priamo od dievčaťa b
        // from[a] == a2 : bol navštívený tak, že sme od chlapca a2 išli
        //                 k dievčaťu match[a2] a od nej ku chlapcovi a

        vector<int> from(A,-1);

        // všetkých chlapcov, ktorí sú ochotní tancovať s dievčaťom b,
        // zaradíme do fronty na spracovanie a nastavíme im from[]

        queue<int> Q;
        for (int a : BA[b]) { Q.push(a); from[a]=a; }

        // kým sa fronta nevyprázdni, prehľadávame

        while (!Q.empty()) {

            // vyberieme ďalšieho chlapca na spracovanie
            // pozrieme sa, či má v aktuálnom párovaní partnerku
            
            int a = Q.front(); Q.pop();

            if (match[a] == -1) {

                // tento chlapec nemá partnerku, našli sme teda zlepšujúcu cestu
                // upravíme podľa nej párovanie -- "o 1 poposúvame" partnerky

                while (from[a] != a) { 

                    // aktuálny chlapec dostane ako partnerku dievča, z ktorého
                    // sme doň prišli -- teda doterajšiu partnerku chlapca from[a]

                    match[a] = match[from[a]]; 

                    // presunieme sa na toho chlapca a úvahu opakujeme, až kým
                    // neprejdeme celú cestu

                    a = from[a]; 
                }

                // na konci zlepšujúcej cesty ešte poslednému chlapcovi dáme ako
                // novú partnerku práve pribudnuvšie dievča b

                match[a] = b;

                // a celé prehľadávanie ukončíme

                break;

            } else {

                // práve spracúvaný chlapec partnerku má, pozrieme sa na ňu
                // všetkých ostatných chlapcov, ktorí sú s ňou ochotní tancovať
                //     a ešte neboli objavení prehľadávaním, zaradíme do fronty
                //     na spracovanie

                for (int x : BA[match[a]]) if (from[x]==-1) { Q.push(x); from[x]=a; }
            }
        }
    }

    // v tomto okamihu máme zostrojené a v poli match[] zapamätané jedno maximálne
    // párovanie, prerobíme ho na zoznam hrán a ten vrátime na výstup

    vector< pair<int,int> > result;
    for (int a=0; a<A; ++a) if (match[a] != -1) result.push_back( { a, match[a] } );
    return result;
}

int main() {
    // malý test: 3 chlapci, 3 dievčatá, chlapec 0 tancuje s hociktorou, 
    // dievča 0 tancuje s hociktorým
    // optimálne párovanie je tvorené dvoma dvojicami, napr. 0-2 a 1-0.

    vector< pair<int,int> > edge_list = { {0,0}, {0,1}, {0,2}, {1,0}, {2,0} };
    cout << find_maximum_matching(3, 3, edge_list).size() << endl;
}