//
//  main.cpp
//  Cuplaj maxim in graf bipartit
//
//  Created by Mara Dascalu on 13/12/2021.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bits/stdc++.h>
#include <map>
#include <list>
#include <set>
#include <tuple>

#define INF INT_MAX
#define NIL 0
#define N  100005
#define M  500001
typedef std::tuple<int, int> tpl;

using namespace std;

ifstream input("cuplaj.in");
ofstream output("cuplaj.out");

class DisjointSets
{
    int no_nodes;
    vector<int> reprez;     //vectorul care retine reprezentantul fiecarui nod

    public:

    void set_no_nodes(int nr) { no_nodes = nr;}
    int get_no_nodes() { return no_nodes;}

    void initialization(int no_node);      //creeaza fiecare nod drept un subarbore
    int reprezentative(int node, int father[]);       //returneaza reprezentantul componentei care il contine pe node
    void reunite(int node1, int node2, int height[], int father[]); //uneste componenta care contine node1 cu cea care contine node2
};

void DisjointSets::initialization(int no_node)
{
    set_no_nodes(no_nodes);

    reprez.push_back(0);
    for (int i = 1 ; i <= no_nodes; i++)
    {
        reprez.push_back(0);
    }
}

int DisjointSets::reprezentative(int node, int father[])
{
    while (father[node])
        node = father[node];
    return node;
}

void DisjointSets::reunite(int node1, int node2, int height[], int father[])
{
    int r1, r2;

    r1 = reprezentative(node1, father);
    r2 = reprezentative(node2, father);

    if (height[r1] > height[r2])
        father[r2] = r1;
    else
    {
        father[r1] = r2;
        if (height[r1] == height[r2])
            height[r2]++;
    }
}

class Graph
{
    int nodes, edges, nodes_l, nodes_r;
    vector<int> adj[N] ;
    vector<tuple<int,int>> adj_weight[N];
    vector<tuple<int,int>> adj_capacity[N];
    bool visited[N] = {0};

    void set_no_nodes(int n) {nodes = n;}
    int get_no_nodes() {return nodes;}
    void set_no_edges(int n) {edges = n;}
    int get_no_edges() {return edges;}

    void addEdges_dg (int no_nodes, int no_edges);
    void addEdges_ug ();
    void addEdges_dg_weight();
    void addEdges_dg_capacity();

    void DFS(int node);     //parcurgerea DFS a grafului
    void afis_adj(int node);       //afisarea vectorului de vectori de adiacenta a nodurilor
    static bool sortByThird (const tuple<int,int,int> &a, const tuple<int,int,int>&b);    //sorteaza vectorul de tupluri coare contine si costul muchiilor dupa al treilea parametru (cost)

    //PROBLEMA BFS INFORARENA: https://infoarena.ro/problema/bfs
    void BFSUtil(int node);    //BFS adaptat pentru a calcula costul de parcurgere al fiecarui nod, plecand dintr-un nod de start

    //PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
    void DFS_biconnectedComponents(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current);     // DFS auxiliar pentru determinarea componentelor biconexe

    //PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
    void calculateIndegree (int indegree[]);       //functie auxiliara sortarii topologice pentru calcularea gradului interior al fiecarui nod
    void topSort(int indegree[], queue<int> queue_ts);      //functia de sortare topologica

    //PROBLEMA HAVEL-HAKIMI
    bool graphExists (vector<int> degree_seq);      //functia care decide daca daca o secventa de numere poate sau nu poate reprezenta o secventa de noduri ale unui graf
    void inputArray (vector<int> &degree_seq);

    //PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
    void inputAPM(vector<tuple<int,int,int>> &weight_edges);
    void APMUtil(vector<tuple<int,int,int>> &weight_edges);

    //PROBLEMA FLUX MAXIM INFOARENA: https://infoarena.ro/problema/maxflow
    bool bfs_maxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[]);
    int Edmonds_Karp(int src, int dst);

    //PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
    void inputRoy_Floyd(int dist[][N]);
    void Roy_FloydUtil(int dist[][N]);
    void outputRoy_Floyd(int dist[][N]);

    //PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
    void dfsUtil(int src, int &dst, int count, int &max_count);
    void dfs_diameter(int src, int &dst,int &max_count);

    //PROBLEMA CUPLAJ MAXIM IN GRAF BIPARTIT INFOARENA: https://infoarena.ro/problema/cuplaj
    bool bfs_hopcroftKarp(int pairU[], int pairV[], int dist[]);
    bool dfs_hopcroftKarp(int u, int pairU[], int pairV[], int dist[]);

public:
    
    Graph(int no_nodes_l, int no_nodes_r, int no_edges);
    Graph(){};

    //PROBLEMA DFS INFOARENA: https://infoarena.ro/problema/dfs
    int connectedComponents();     //determinarea numarului de componente conexe ale grafului

    //PROBLEMA BFS INFORARENA: https://infoarena.ro/problema/bfs
    void BFS();

    //PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
    void biconnectedComponents();     //determina componentele biconexe ale unui graf

    //PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
    void topologicalSort();

    //PROBLEMA HAVEL-HAKIMI
    void Havel_Hakimi();

    //PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
    void APM();

    //PROBLEMA PADURI DE MULTIMI DISJUNCTE INFOARENA: https://infoarena.ro/problema/disjoint
    void disjoint();

    //PROBLEMA ALGORITMUL LUI DIJKSTRA INFOARENA: https://infoarena.ro/problema/dijkstra
    void Dijkstra();

    //PROBLEMA ALGORITMUL BELLMAN-FORD: https://infoarena.ro/problema/bellmanford
    void Bellman_Ford();

    //PROBLEMA FLUX MAXIM INFOARENA: https://infoarena.ro/problema/maxflow
    int maxFlow ();

    //PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
    void Roy_Floyd();

    //PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
    int diameter();

    //PROBLEMA CICLU EULERIAN INFOARENA: https://infoarena.ro/problema/ciclueuler
    vector<int> Euler();
    
    //PROBLEMA CUPLAJ MAXIM IN GRAF BIPARTIT INFOARENA: https://infoarena.ro/problema/cuplaj
    int hopcroftKarp();
}g;

Graph::Graph(int no_nodes_l, int no_nodes_r, int no_edges)
{
    this->nodes_l = no_nodes_l;
    this->nodes_r = no_nodes_r;
    this->edges = no_edges;
}

void Graph::DFS(int node)
{
    visited[node] = 1;
    output<<node<<" ";

    for (int i = 0; i < adj[node].size(); i++)
        if( !visited[adj[node][i]])
            DFS(adj[node][i]);
}

void Graph::afis_adj(int node)
{
    for (int i = 0; i < adj[node].size(); i++)
         cout<<adj[node][i]<<" ";
}

void Graph::addEdges_dg (int no_nodes, int no_edges)
{
//       int no_nodes, no_edges;
//       input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2;

    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2;
        adj[node1].push_back(node2);
    }
}

void Graph::addEdges_ug ()
{
    int no_nodes;
    input>>no_nodes;
    set_no_nodes(no_nodes);

    int node1, node2;

    while (input>>node1>>node2) {
        adj[node1].push_back(node2);
        adj[node2].push_back(node1);
    }
}

void Graph::addEdges_dg_weight()
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2, weight;

    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2>>weight;
        adj_weight[node1].push_back(make_tuple(node2, weight));
    }
}

void Graph::addEdges_dg_capacity()
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2, capacity;
    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2>>capacity;
        adj_capacity[node1].push_back(make_tuple(node2, capacity));
    }
}

int Graph::connectedComponents ()
{
    int cc = 0;
    for (int i = 1; i <= get_no_nodes(); i++)
        if (!visited[i])
        {
            cc++;
            DFS(i);
        }
    return cc;
}

void Graph::BFSUtil (int node)
{
    int cost[N];
    queue<int> queue_bfs;

    memset(cost,  -1, sizeof(cost));

    visited[node] = 1; //marchez nodul curent ca vizitat
    queue_bfs.push(node);
    cost[node] = 0;

    while (!queue_bfs.empty()) {
        node = queue_bfs.front(); //iau nodul din varful cozii
        queue_bfs.pop();

        for (int i = 0; i < adj[node].size(); i++) //parcurg toti vecinii sai
            if ( !visited[adj[node][i]]) //daca sunt nevizitati
            {
                visited[adj[node][i]] = 1;  //ii marchez ca vizitati
                queue_bfs.push(adj[node][i]);   //ii adaug in coada
                cost[adj[node][i]] = cost[node] + 1;   //calculez costul raportat la "parintele" sau
            }
    }

    for (int i = 1; i <= get_no_nodes(); i++)
        output<<cost[i]<<" ";
}

void Graph::BFS()
{
    int no_nodes, no_edges, start;
        input>>no_nodes>>no_edges>>start;
        
        g.addEdges_dg(no_nodes, no_edges);
        g.BFSUtil(start);
}

void Graph::DFS_biconnectedComponents(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current)
{
    visited[node] = 1;

    level[node] = level[parent] + 1;
    low_level[node] = level[node];
    int child;

    int dim = adj[node].size();
    for ( int i = 0; i< dim ; i++)
    {
        child = adj[node][i];
        if (child != parent)
        {
            if (visited[child] == true)  //daca fiul sau a fost deja parcurs si nu este tatal nodului curent, muchia (fiu,nod) este muchie de intoarcere
            {
                if(level[child] < low_level[node])low_level[node] = level[child];  //actualizam valoarea low_level[nod] daca fiul sau se afla mai sus decat el (pt ca avem muchie de intoarcere)
            }
            else //daca fiul sau nu a fost inca parcurs, continuam DFS din fiu
            {
                component_node.push({node, child});
                DFS_biconnectedComponents(child, node, level, low_level, bcc, component_node, current);

                if (low_level[child] < low_level[node])
                    low_level[node] = low_level[child]; //daca la intoarcerea din apel fiul are un nivel de intoarcere mai mic decat al nodului, actualizam low_level[node]

                if (low_level[child] >= level[node])        //nodul k este pct de articulatie
                {
                    bcc.push_back({});
                    while( component_node.top().first != node)
                    {
                        bcc.back().push_back(component_node.top().second);
                        component_node.pop();
                    }
                    bcc.back().push_back(component_node.top().second);
                    bcc.back().push_back(component_node.top().first);
                    component_node.pop();
                    current++;
               }
            }
        }
    }
}

void Graph::biconnectedComponents()
{
    int level[N] = {0};    //nivelul la care se afla un nod
    int low_level[N] = {0};    //nivelul minim de intoarcere a unui nod
    stack<pair<int, int>> component_node;
    vector<vector<int>> bcc; //vectorul care stocheaza componentele biconexe
    int current = 0;

    DFS_biconnectedComponents(1,0, level, low_level, bcc, component_node, current);

    output<<current << "\n";
    for (int i =0 ; i <= current; i++)
        {
            for (int j = bcc[i].size() - 1; j >= 0; j--)
                if(bcc[i][j])
                    output<<bcc[i][j]<<" ";
            output<<"\n";
        }
}

void Graph::calculateIndegree (int indegree[])
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);

    int node1, node2;
    memset(indegree, 0, no_nodes);

    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2;
        adj[node1].push_back(node2);
        indegree[node2]++;
    }
}

void Graph::topSort(int indegree[], queue<int> queue_ts)
{
    int dim = get_no_nodes();
    for (int i = 1; i <= dim ; i++)  //adaugam in coada doar nodurile care au gradul 0
    {
        if (indegree[i] == 0)
            queue_ts.push(i);
    }

    while (!queue_ts.empty()) //cat timp coada nu este goala, extragem varful, scadem gradele nodurilor adiacente cu varful si adaugam in coada acele noduri care au gradul interior 0
    {
        int node = queue_ts.front();
        queue_ts.pop();

        for (int i = 0; i < adj[node].size(); i++)
        {
            int adj_node = adj[node][i];
            indegree[adj_node]--;
            if (!indegree[adj_node])
                queue_ts.push(adj_node);
        }
        cout<<node<<" ";
    }
}

void Graph::topologicalSort()
{
    queue<int> queue_ts; //coada in care vom adauga doar nodurile care au gradul interior 0
    int indegree[N] ; //vectorul care retine gradul interior al fiecarui nod

    calculateIndegree(indegree);
    topSort(indegree, queue_ts);
    }

    bool Graph::graphExists (vector<int> degree_seq)
    {
    while (1) {
        sort(degree_seq.begin(), degree_seq.end(), greater<>());
        cout<<degree_seq[0]<<" ";
        if (degree_seq[0] == 0)  //daca toate elementele ramase sunt 0, atunci se poate construi un graf
            return true;

        int top = degree_seq[0];
        degree_seq.erase(degree_seq.begin());

        if (top > degree_seq.size()) // daca valoarea primului element este mare decat numarul de elemente ramase, nu putem construi un astfel de graf
            return false;

        for (int i = 0 ; i < degree_seq.size(); i++) //dupa eliminarea primului element, scadem gradul "nodurilor" ramase
        {
            degree_seq[i]--;
            if(degree_seq[i] < 0)  //daca apar numere negative, nu putem sa construim un graf
                return false;
        }
    }
}

void Graph::inputArray (vector<int> &degree_seq)
{
    int n;
    input>>n;

    for (int i = 0; i < n; i++)
    {
        int val;
        input>>val;
        degree_seq.push_back(val);
    }
}

void Graph::Havel_Hakimi()
{
    vector<int> degree_seq; //vectorul care contine gradele unui posibil graf

    inputArray(degree_seq);
    output<<graphExists(degree_seq);
}

bool Graph::sortByThird (const tuple<int,int,int> &a, const tuple<int,int,int>&b)
{
    return (get<2>(a) < get<2>(b));
}

void Graph::inputAPM(vector<tuple<int,int,int>> &weight_edges)
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    for (int i = 0 ; i < no_edges; i++)
    {
        int n1, n2, weight;
        input>>n1>>n2>>weight;
        weight_edges.push_back(make_tuple(n1,n2,weight));
    }
}

void Graph::APMUtil(vector<tuple<int,int,int>> &weight_edges)
{
//    sort(weight_edges.begin(), weight_edges.end(), sortByTh);   //sortam vectorul crescator in functie de cost
//
//    DisjointSets djs;
//    djs.initialization(get_no_nodes());     //consideram ca fiecare nod reprezinta un subarbore
//
//    int weight = 0;     //costul arborelui
//    int ctr = 0;        //numarul de muchii ale APM intr-un anumit moment
//    vector<tuple<int,int>> apm;
//    for (int i = 0; i < get_no_edges(); i++)
//    {
//        int n1 = get<0>(weight_edges[i]);       //la fiecare iteratie alegem muchia cu cost minim
//        int n2 = get<1>(weight_edges[i]);
//
//        int r1 = djs.reprezentative(n1);        //verificam reprezentantii nodurilor incidente acestei muchii
//        int r2 = djs.reprezentative(n2);
//
//        if (r1 != r2)       //daca avem reprezentanti diferiti, subarborii din care fac parte nodurile se reunesc; altfe,l, ignoram muchia, deoarece ar genera un ciclu in APM
//        {
//            apm.push_back(make_tuple(n1, n2));
//            ctr++;
//            weight += get<2>(weight_edges[i]);
//            djs.reunite(n1, n2);
//
//            if  (ctr == get_no_nodes() - 1)      //un arbore poate avea maximum n-1 muchii intre noduri; astfel, daca am gasit n-1 muchii putem opri cautarea
//                break;
//        }
//    }
//
//    output<<weight<<"\n";
//    output<<get_no_nodes() - 1<<"\n";
//    for (int i = 0; i < apm.size(); i++)
//        output<<get<0>(apm[i])<<" "<<get<1>(apm[i])<<"\n";
}

void Graph::APM()
{
    vector<tuple<int,int,int>> weight_edges;

    inputAPM(weight_edges);
    APMUtil(weight_edges);

}

void Graph::disjoint()
{
    int height[N] = {0};
    int father[N] = {0};

    int no_sets, no_tasks;
    input>>no_sets>>no_tasks;

    DisjointSets djs;

    for (int i = 0; i < no_tasks; i++)
    {
        int no_task,x,y;
        input>>no_task>>x>>y;

        if (no_task == 1)
            djs.reunite(x, y, height, father);
        else
        {
            int r1 = djs.reprezentative(x, father);
            int r2 = djs.reprezentative(y, father);

            if(r1 != r2)
                output<<"NU\n";
            else output<<"DA\n";
        }
    }
}

void Graph::Dijkstra()
{
    int dist[N];       //vectorul care retine distanta minima de la nodul de start la celelalte noduri
    int start = 1;
    priority_queue<tpl, vector<tpl>, greater<tpl>> queue_adj;   //coada in care retinem nodurile adiacente si costurile muchiilor de adiacenta ale nodului vizitat curent pentru a avea ordinea parcurgerii
                                                                //vom retine mai intai costul si apoi nodul adiacent pentru a putea obtine cu usurinta la fiecare iteratie nodul care are muchia asociata de cost minim

    for (int i = 1; i <= get_no_nodes(); i++)
        dist[i] = INF;

    queue_adj.push(make_tuple(0, start));   //pentru nodul de start avem costul 0 pentru a ajunge la el
    dist[start] = 0;

    while (!queue_adj.empty()) {
        int node = get<1>(queue_adj.top());
        queue_adj.pop();

        for (int i = 0; i < adj_weight[node].size(); i++)       //pentru toate nodurile adiacente ale lui node
        {
            int child = get<0>(adj_weight[node][i]);
            int weight = get<1>(adj_weight[node][i]);

            if (dist[node] + weight < dist[child])      //verificam daca pentru nodurile adiacente gasim un drum mai scurt prin node decat cele parcurse deja
            {
                dist[child] = dist[node] + weight;
                queue_adj.push(make_tuple(dist[child], child));
            }
        }
    }

    for (int i = 2; i <= get_no_nodes(); i++)
        if (dist[i] == INF)
            output<<"0 ";
        else output<<dist[i]<<" ";
}

void Graph::Bellman_Ford()
{
    int dist[N];  //vectorul care retine distanta minima de la nodul de start(1) la toate celelalte noduri
    int len[N] = {0};  //vectorul care memoreaza lungimea unui drum de la sursa la un alt nod
    queue<int> queue_bf;        //coada care memoreaza nodurile ale caror distanta minima s-a modificat
    int start = 1;
    bool cycle = false;        //presupunem ca in graf nu exista cicluri negative

    for (int i = 1; i <= get_no_nodes(); i++)
        dist[i] = INF;

    dist[start] = 0;        //pentru nodul 1 avem costul 0 pentru a ajunge la el
    queue_bf.push(start);

    while (!queue_bf.empty() && !cycle)
    {
        int node = queue_bf.front();
        queue_bf.pop();

        for (int i = 0; i < adj_weight[node].size(); i++)  //pentru toate nodurile adiacente cu node
        {
            int child = get<0>(adj_weight[node][i]);
            int weight = get<1>(adj_weight[node][i]);

            if (dist[node] + weight < dist[child])      //verificam daca gasim un drum mai scurt decat cel parcurs deja
            {
                len[child] = len[node] + 1;
                if (len[child] == get_no_nodes())   //daca obtinem o lungime mai mare sau egala cu n, inseamna ca in graf exista un ciclu negativ
                {
                    cycle = true;
                    break;
                }
                dist[child] = dist[node] + weight;
                queue_bf.push(child);
            }
        }
    }

    if (cycle)
        output<<"Ciclu negativ!";
    else
        for (int i = 2; i <= get_no_nodes(); i++)
            output<<dist[i]<<" ";
}

bool Graph::bfs_maxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[])
{
    memset(visited, false, sizeof(visited));

    queue<int> q;
    q.push(src);
    visited[src] = true;        //marcam nodul curent ca vizitat
    parent[src] = 0;

    while (!q.empty())
    {
        int node = q.front();       //luam primul element din coada
        q.pop();
        
        for (int i = 0 ; i < adj_capacity[node].size(); i++)        //parcurg toate nodurile adiacente cu nodul curent
        {
            int j = get<0>(adj_capacity[node][i]);
            if (!visited[j] && residualGraph[node][j] > 0)
            {
                if (j == dst)       //daca am gasit un drum de la sursa la destinatie, ne oprim cu bfs_maxFlow
                {
                    parent[j] = node;
                    return true;
                }
                q.push(j);
                parent[j] = node;
                visited[j] = true;
            }
        }
    }
    return false;
}

int Graph::Edmonds_Karp(int src, int dst)
{
    vector<vector<int>> residualGraph;        //cream un graf rezidual pe care il initializam cu valorile capacitatilor din graful original
                                    //residualGraph[i][j] -> capacitatea arcului de la i la j, daca acesta exista
    int parent[get_no_nodes() + 1];         //vectoul folosit pentru a memora drumul de la sursa la destinatie
    int max_flow = 0;       //initial nu avem niciun flux
    residualGraph.resize(get_no_nodes() + 1, vector<int> (get_no_nodes() + 1, 0));
    for (int i = 1; i <= get_no_nodes(); i++)
        for (int j = 0; j < adj_capacity[i].size(); j++)
        {
            int col = get<0>(adj_capacity[i][j]);
            residualGraph[i][col] = get<1>(adj_capacity[i][j]);
        }

    while (bfs_maxFlow(src, dst, residualGraph, parent)) {      //cat timp avem drum de la sursa la destinatie
        //cautam capacitatea reziduala minima a fiecarui arc de-a lungul drumului gasit de bfs
        int path_flow = INT_MAX;
        for (int i = dst ; i != src; i = parent[i])
        {
            int node = parent[i];
            path_flow = min(path_flow, residualGraph[node][i]);
        }
        
        //modificam valorile reziduale ale arcelor directe si inverse care se afla pe drumul gasit de bfs
        for (int i = dst ; i != src; i = parent[i])
        {
            int node = parent[i];
            residualGraph[node][i] -= path_flow;
            residualGraph[i][node] += path_flow;
        }
        max_flow += path_flow;
    }
    return max_flow;
}

int Graph::maxFlow()
{
    addEdges_dg_capacity();
    return Edmonds_Karp(1, get_no_nodes());
}

void Graph::Roy_FloydUtil(int dist[][N])
{
    int n = get_no_nodes();
    for (int k = 1; k <= n; k++)       //consideram pe rand fiecare nod ca fiind intermediar
        for (int i = 1; i <= n; i++)       //consideram pe rand ca fiecare nod este sursa
            for (int j = 1; j <= n; j++)       //consideram pe rand fiecare nod ca fiind destinatie
                if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF && dist[i][k] != INF)) {     //modificam distanta
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
}

void Graph::outputRoy_Floyd(int dist[][N])
{
    for (int i = 1; i <= get_no_nodes(); i++)
    {
        for (int j = 1; j <= get_no_nodes(); j++)
            if (dist[i][j] == INF || i == j)
                output<<"0 ";
            else
                output<<dist[i][j]<<" ";
        output<<"\n";
    }
}

void Graph::inputRoy_Floyd(int dist[][N])
{
    int no_nodes;
    input>>no_nodes;
    set_no_nodes(no_nodes);

    for (int  i = 1; i <= no_nodes; i++)
        for (int j = 1; j <= no_nodes; j++)
    {
        input>>dist[i][j];
        if (!dist[i][j]) dist[i][j] = INF;
    }
}

void Graph::Roy_Floyd()
{
    int dist[N][N];      // dist este matricea rezultat care contine drumul minim intre toate perechile de noduri
    inputRoy_Floyd(dist);
    Roy_FloydUtil(dist);
    outputRoy_Floyd(dist);
}

void Graph::dfsUtil(int src, int &dst, int count, int &max_count)
{
    visited[src] = true;
    count++;
    for (int i = 0; i < adj[src].size(); i++)
    {
        if (!visited[adj[src][i]]){
            if (count >= max_count)
            {
                max_count = count;
                dst = adj[src][i];
            }
            dfsUtil(adj[src][i], dst, count, max_count);
        }
    }
}

void Graph::dfs_diameter(int src, int &dst, int &max_count)
{
    int count = 0;
    for (int i = 1 ; i <= get_no_nodes(); i++)
        visited[i] = false;

    dfsUtil(src, dst, count + 1, max_count);
}

int Graph::diameter()
{
    addEdges_ug();
    int max_count = INT_MIN;
    int src, dst;

    dfs_diameter(1, dst, max_count);
    dfs_diameter(dst, src, max_count);

    return max_count;
}

vector<int>Graph::Euler()
{
    vector<tpl> edges[N];       //vector of adjacent nodes; for each edge, it stores a unique code for easier identification of each edge
    bool eliminated[M] = {false};       //if we eliminate an edge, eliminated[edge_code] becomes true
    stack<int> stack_euler;
    vector<int> eulerCircuit;
    
    int no_nodes, no_edges;
    input >> no_nodes >> no_edges;
    
    for (int i = 0 ; i < no_edges ; i++)
    {
        int x, y;
        input>>x>>y;
        edges[x].push_back(make_tuple(y,i));
        edges[y].push_back(make_tuple(x,i));
    }
    
    for (int i = 1 ; i <= no_nodes ; i++)
    {
        if (edges[i].size() % 2)        //if the graph contains odd vertices, then it can't have an euler circuit
        {
            eulerCircuit.push_back(-1);
            return eulerCircuit;
        }
    }
    
    stack_euler.push(1);        //we simulate the recursion using a stack
    while (!stack_euler.empty())
    {
        int node = stack_euler.top();
        if (!edges[node].empty())       //if the current node still has adjacent nodes
        {
            tpl t = edges[node].back();
            edges[node].pop_back();
            
            int adj_node = get<0>(t);
            int edge_code = get<1>(t);
            
            if (!eliminated[edge_code])
            {
                eliminated[edge_code] = true;       //we eliminate the edge
                stack_euler.push(adj_node);         //and continue the recursion from the adjacent node
            }
        }
        else    //the node can be added to the euler circuit
        {
            stack_euler.pop();
            eulerCircuit.push_back(node);
        }
    }
    eulerCircuit.pop_back();
    
    return eulerCircuit;
}

bool Graph::bfs_hopcroftKarp(int pairU[], int pairV[], int dist[])
{
    queue<int> q;
    
    for (int u = 1 ; u <= nodes_l ; u++)
    {
        if (pairU[u] == NIL)
        {
            dist[u] = 0;
            q.push(u);
        }
        else
        {
            dist[u] = INF;
        }
    }
    
    dist[NIL] = INF;
    
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        
        if (dist[u] < dist[NIL])
        {
            for (int i = 0 ; i < adj[u].size() ; i++)
            {
                int v = adj[u][i];
                
                if (dist[pairV[v]] == INF)
                {
                    dist[pairV[v]] = dist[u] + 1;
                    q.push(pairV[v]);
                }
            }
        }
    }
    
    return (dist[NIL] != INF);
}

bool Graph::dfs_hopcroftKarp(int u, int pairU[], int pairV[], int dist[])
{
    if (u != NIL)
    {
        for (int i = 0 ; i < adj[u].size() ; i++)
        {
            int v = adj[u][i];
            
            if (dist[pairV[v]] == dist[u] + 1)
            {
                if (dfs_hopcroftKarp(pairV[v], pairU, pairV, dist))
                {
                    pairV[v] = u;
                    pairU[u] = v;
                    return true;
                }
            }
        }
        
        dist[u] = INF;
        return false;
    }
    return true;
}

int Graph::hopcroftKarp()
{
    for (int i = 0 ; i < edges ; i++)
    {
        int x, y;
        input >> x >> y;
        adj[x].push_back(y);
    }
    
    int pairU[nodes_l + 1];       //stores pair of u in matching where u is a vertex on left side of bipartite graph
    int pairV[nodes_r + 1];       //stores pair of v in matching where v is a vertex on right side of bipartite graph
    int dist[nodes_l + 1];        //stores distance of left side vertices
    
    for (int i = 0 ; i <= nodes_l ; i++)
        pairU[i] = NIL;
    for (int j = 0; j <= nodes_r; j++)
        pairV[j] = NIL;
    
    int result = 0;
    
    while (bfs_hopcroftKarp(pairU, pairV, dist))
    {
        for (int u = 1 ; u <= nodes_l ; u++)
        {
            if (pairU[u] == NIL && dfs_hopcroftKarp(u, pairU, pairV, dist))
            {
                result++;
            }
        }
    }
    
    return result;
}

int main(int argc, const char * argv[])
{
    int no_nodes_l, no_nodes_r, no_edges;
    input >> no_nodes_l >> no_nodes_r >> no_edges;

    Graph g1(no_nodes_l, no_nodes_r, no_edges);
    output << g1.hopcroftKarp();
}