#include <bits/stdc++.h>
#define NIL -1
#define INFINIT INT_MAX

using namespace std;

ifstream fin("maxflow.in");
ofstream gout("maxflow.out");

typedef pair<int, int> pereche;

class Graful_meu
{
    int _noduri;
    int _muchii;
    vector<vector<pereche>> lista_adiacenta;
    bool _directed, _weighted;

private:
    void DFS(int start, bool vizitat[]);
    void DFS_Componente_Biconexe(int nod_curent, stack<int>&stiva_noduri, vector<int>&low, vector<int>&discovery_time, vector<vector<int>>&all_biconex_components);
    void DFS_Componente_Tare_Conexe(int nod_curent, stack<int>&stiva_noduri, vector<bool>&is_part_of_a_connected_comp, vector<int>&low, vector<int>&discovery_time, vector<vector<int>>&all_strongly_connected_components);
    void DFS_Critical_Connections(int nod_curent, int parinte, vector<int>&low, vector<int>&discovery_time, vector<vector<int>>&all_output_components);
    int find_radacina(int nod, vector<int>&tata);
    void union_radacini(int nod1, int nod2, vector<int>&tata);
    int bfs_Edmonds_Karp_Algorithm(int sursa, int destinatie, vector<int> &tata, vector<vector<int>>&capacitate_reziduala);

public:
    Graful_meu(int noduri = 0, int muchii = 0, bool directed = false, bool weighted = false);

    void citire_graf();
    int getter_numar_noduri();

    int Componente_conexe();
    vector<int> BFS(int start);
    vector <vector<int>> Componente_Biconexe();
    vector<vector<int>> Componente_Tare_Conexe();
    vector<vector<int>> criticalConnections();
    vector<int> TopologicalSort();
    bool Havel_Hakimi(int n, vector<int>&grade);

    // tema - part 2
    vector<int> Prim_Algorithm(int &total_weight);
    void paduri_multimi_disjuncte();
    vector<pereche> Kruskal_Algorithm(int &total_weight);
    vector<int> Dijkstra_Algorithm();
    vector<int> Bellman_Ford_Algorithm();

    // tema - part 3
    vector<vector<long long>> Roy_Floyd_Algorithm();
    int diametru_arbore();
    int maxFlow_Edmonds_Karp_Algorithm(int sursa, int destinatie);
};
Graful_meu::Graful_meu(int noduri, int muchii, bool directed, bool weighted)
{
    _noduri = noduri;
    _muchii = muchii;
    _directed = directed;
    _weighted = weighted;
    lista_adiacenta.resize(_noduri + 2);
}
void Graful_meu::citire_graf()
{
    int x, y;
    int cost = 0;
    for(int i = 1 ; i <= _muchii ; ++i)
    {
        fin >> x >> y;
        if(_weighted)
            fin >> cost;
        lista_adiacenta[x].push_back({y, cost});
        if(!_directed)
            lista_adiacenta[y].push_back({x, cost});
    }
}

int Graful_meu::getter_numar_noduri()
{
    return _noduri;
}

// parcurgere DFS
void Graful_meu::DFS(int start, bool vizitat[])
{
    vizitat[start] = 1;
    for(auto nod_vecin : lista_adiacenta[start])
        if(vizitat[nod_vecin.first] == 0)
            DFS(nod_vecin.first, vizitat);

}

// se va returna numarul de componente conexe, folosindu-ne de functia DFS
int Graful_meu::Componente_conexe()
{
    bool vizitat[_noduri + 2] = {0};
    int numar_componente_conexe = 0;
    for(int i = 1 ; i <= _noduri ; ++i)
        if (vizitat[i] == 0)
        {
            DFS(i, vizitat);
            ++numar_componente_conexe;
        }
    return numar_componente_conexe;
}

// parcurgerea BFS
vector<int> Graful_meu::BFS(int start)
{
    bool vizitat[_noduri + 2] = {0};
    queue<int>coada_BFS;
    vector<int> drumuri_minime(_noduri + 2, -1);

    coada_BFS.push(start);
    vizitat[start] = 1;
    drumuri_minime[start] = 0;

    while(!coada_BFS.empty())
    {

        for(auto nod_vecin : lista_adiacenta[start])
            if(vizitat[nod_vecin.first] == 0)
            {
                coada_BFS.push(nod_vecin.first);
                vizitat[nod_vecin.first] = 1;
                drumuri_minime[nod_vecin.first] = drumuri_minime[start] + 1;
            }
        coada_BFS.pop();
        start = coada_BFS.front();
    }

    return drumuri_minime;
}

// functia va returna fiecare vector de noduri care compun o componenta biconexa, ne ajutam de un DFS modificat
vector<vector<int>> Graful_meu::Componente_Biconexe()
{
    vector<int>discovery_time(_noduri + 2, NIL);
    vector<int>low(_noduri + 2, NIL);
    vector<vector<int>> all_biconex_components;
    stack<int>stiva_noduri;

    for(int i = 1 ; i <= _noduri ; ++i)
        if(discovery_time[i] == NIL)
            DFS_Componente_Biconexe(i, stiva_noduri, low, discovery_time, all_biconex_components);

    return all_biconex_components;
}

// in functie verificam daca nodul curent este sau nu punct de articulatie(nod critic)
// o idee adaptata pornind de la aceasta: un nod este critic daca are un fiu care are nivelul de intoarcere >= ca nivelul nodului(tata)
void Graful_meu::DFS_Componente_Biconexe(int nod_curent, stack<int>&stiva_noduri, vector<int>&low,
                                        vector<int>&discovery_time,vector<vector<int>>&all_biconex_components)
{
    static int time = 0;
    low[nod_curent] = discovery_time[nod_curent] = ++time;
    stiva_noduri.push(nod_curent);

    for(auto vecin : lista_adiacenta[nod_curent])
    {
        if(discovery_time[vecin.first] == NIL)
        {
            DFS_Componente_Biconexe(vecin.first, stiva_noduri, low, discovery_time, all_biconex_components);

            low[nod_curent] = min(low[nod_curent], low[vecin.first]);
            if(low[vecin.first] >= discovery_time[nod_curent])
            {
                vector<int>one_biconex_component;
                int nod_stiva = stiva_noduri.top();
                stiva_noduri.pop();
                one_biconex_component.push_back(nod_stiva);
                while(nod_stiva != vecin.first)
                {
                    nod_stiva = stiva_noduri.top();
                    stiva_noduri.pop();
                    one_biconex_component.push_back(nod_stiva);
                }
                one_biconex_component.push_back(nod_curent);

                all_biconex_components.push_back(one_biconex_component);
            }
        }
        else
            low[nod_curent] = min(low[nod_curent], discovery_time[vecin.first]);
    }
}

// functia va returna fiecare vector de noduri care compun o componenta tare conexa, ne ajutam de un DFS modificat
vector<vector<int>> Graful_meu::Componente_Tare_Conexe()
{
    vector<int>discovery_time(_noduri + 2, NIL);
    vector<int>low(_noduri + 2, NIL);
    vector<vector<int>> all_strongly_connected_components;
    stack<int>stiva_noduri;
    vector<bool>is_part_of_a_connected_comp(_noduri + 2, false);

    for(int i = 1 ; i <= _noduri ; ++i)
        if(discovery_time[i] == NIL)
            DFS_Componente_Tare_Conexe(i, stiva_noduri, is_part_of_a_connected_comp, low, discovery_time, all_strongly_connected_components);

    return all_strongly_connected_components;
}

// aceasta functie are ca scop determinarea fiecarei radacini a componentelor tare conexe,
// mai precis in if-ul acela unde testam daca low[vecin] == discovery_time[nod_curent]
void Graful_meu::DFS_Componente_Tare_Conexe(int nod_curent, stack<int>&stiva_noduri, vector<bool>&is_part_of_a_connected_comp, vector<int>&low,
                                        vector<int>&discovery_time,vector<vector<int>>&all_stongly_connected_components)
{
    static int time = 0;
    low[nod_curent] = discovery_time[nod_curent] = ++time;
    stiva_noduri.push(nod_curent);

    for(auto vecin : lista_adiacenta[nod_curent])
    {
        if(discovery_time[vecin.first] == NIL)
        {
            DFS_Componente_Tare_Conexe(vecin.first, stiva_noduri, is_part_of_a_connected_comp, low, discovery_time, all_stongly_connected_components);

            low[nod_curent] = min(low[nod_curent], low[vecin.first]);
        }
        else
            if(is_part_of_a_connected_comp[vecin.first] == false)
                low[nod_curent] = min(low[nod_curent], discovery_time[vecin.first]);
    }

    if(low[nod_curent] == discovery_time[nod_curent])
    {
        vector<int>one_strongly_connected_component;
        int nod_stiva = stiva_noduri.top();
        while(nod_stiva != nod_curent)
        {
            one_strongly_connected_component.push_back(nod_stiva);
            is_part_of_a_connected_comp[nod_stiva] = true;
            stiva_noduri.pop();
            nod_stiva = stiva_noduri.top();
        }
        one_strongly_connected_component.push_back(nod_stiva);
        is_part_of_a_connected_comp[nod_stiva] = true;
        stiva_noduri.pop();

        all_stongly_connected_components.push_back(one_strongly_connected_component);
    }
}

// functie ce returneaza toate muchiile critice
vector<vector<int>> Graful_meu::criticalConnections()
{
        vector<vector<int>> lista_adiacenta(_noduri + 2);
        vector<int>discovery_time(_noduri + 2, NIL);
        vector<int>low(_noduri + 2, NIL);
        vector<vector<int>>all_output_components;

        for(int i = 1 ; i <= _noduri ; ++i)
            if(discovery_time[i] == -1)
                DFS_Critical_Connections(i, -1, low, discovery_time, all_output_components);
        return all_output_components;
}

// functia este un DFS adaptat care se bazeaza pe urmatoarea idee:
// o muchie este critica daca nivelul de intoarcere(un fel de nivel de intoarcere: low) al fiului(vecin) > ca nivelul tatalui (nod_curent)
void Graful_meu::DFS_Critical_Connections(int nod_curent, int parinte, vector<int>&low, vector<int>&discovery_time,
                                                vector<vector<int>>&all_output_components)
    {
        static int time = 0;
        low[nod_curent] = discovery_time[nod_curent] = ++time;

        for(auto vecin : lista_adiacenta[nod_curent])
        {
            if(discovery_time[vecin.first] == NIL)
            {
                parinte = nod_curent;
                DFS_Critical_Connections(vecin.first, parinte, low,discovery_time, all_output_components);
                low[nod_curent] = min(low[nod_curent], low[vecin.first]);

                if(low[vecin.first] > discovery_time[nod_curent])
                    all_output_components.push_back({nod_curent, vecin.first});
            }
            else
                if(parinte != vecin.first)
                    low[nod_curent] = min(low[nod_curent], discovery_time[vecin.first]);
        }
    }

// sortarea topologica (metoda de implementare fix ca la curs, NU cea cu un DFS)
vector<int> Graful_meu::TopologicalSort()
{
    int grad_interior[_noduri + 2] = {0};
    vector<int>ordine_topologica;

    for(int i = 1 ; i <= _noduri ; ++i)
        for(auto vecin : lista_adiacenta[i])
            ++grad_interior[vecin.first];

    int copie_numar_noduri = _noduri;
    while(copie_numar_noduri)
    {
        for(int nod_curent = 1 ; nod_curent <= _noduri ; ++nod_curent)
        {
            if(grad_interior[nod_curent] == 0)
            {
                ordine_topologica.push_back(nod_curent);
                for(auto vecin : lista_adiacenta[nod_curent])
                    --grad_interior[vecin.first];
                grad_interior[nod_curent] = NIL;
                --copie_numar_noduri;
            }
        }
    }
    return ordine_topologica;
}

// algoritmul lui Havel Hakimi care ne va spune daca se poate forma un graf din vectorul de grade
bool Graful_meu::Havel_Hakimi(int n, vector<int>&grade)
{
    int suma = 0;
    for(auto element : grade)
    {
        suma += element;
        if(element > n - 1)
            return false;
    }
    if(suma % 2)
       return false;

    while(all_of(grade.begin(), grade.end(), [](int i) {return i == 0;}) == false)
    {
        sort(grade.begin(), grade.end(), greater<int>());
        int valoare_grad = grade[0];
        grade.erase(grade.begin());
        for(int i = 0 ; i < valoare_grad ; ++i)
        {
            --grade[i];
            if(grade[i] < 0)
                return false;
        }
    }
    return true;

}

// algoritmul lui Prim implementat cu priority queue, va returna vectorul de tati si va calcula costul total pe parcursul adaugarii in APM
vector<int> Graful_meu::Prim_Algorithm(int &total_weight)
{
    priority_queue<pereche, vector<pereche>, greater<pereche>> min_heap;
    vector<int> cost(_noduri + 2, INFINIT);
    vector<int> tata(_noduri + 2, NIL);
    vector<bool> inAPM(_noduri + 2, false);
    total_weight = 0;

    min_heap.push({0, 1});
    cost[1] = 0;

    while(!min_heap.empty())
    {
        int nod_curent = min_heap.top().second;
        int cost_curent = min_heap.top().first;
        min_heap.pop();

        if(inAPM[nod_curent] == true)
            continue;

        total_weight += cost_curent;
        inAPM[nod_curent] = true;
        for(auto vecin : lista_adiacenta[nod_curent])
        {
            int cost_vecin = vecin.second;
            int nod_vecin = vecin.first;

            if(inAPM[nod_vecin] == false and cost[nod_vecin] > cost_vecin)
            {
                cost[nod_vecin] = cost_vecin;
                min_heap.push({cost_vecin, nod_vecin});
                tata[nod_vecin] = nod_curent;
            }
        }
    }

    return tata;
}

// returneaza radacina arborelui in care se afla nodul din argument(nodul curent)
// VARIANTA OPTIMIZATA - legam toate nodurile pe parcursul recursiei de radacina arborelui din care fac parte, adica sa avem toate
// nodurile din arborele respectiv pe un nivel(inafara de radacina Obvious)
int Graful_meu::find_radacina(int nod, vector<int>&tata)
{
    if(nod == tata[nod])
        return nod;
    return tata[nod] = find_radacina(tata[nod], tata);
}
//unim radacinile a doi arbori diferiti
void Graful_meu::union_radacini(int nod1, int nod2, vector<int>&tata)
{
    tata[nod1] = tata[nod2];
}
// daca ni se da operatie de tip 1 - unim arborii (stim din cerinta ca cele doua noduri nu vor fi din acelasi arbore)
//                           tip 2 - afisam "DA" daca fac parte din acelasi arbore, else "NU" daca sunt din arbori diferiti
void Graful_meu::paduri_multimi_disjuncte()
{
    vector<int>tata(_noduri + 2);
    for (int i = 1 ; i <= _noduri ; ++i)
        tata[i] = i;

    for (int i = 1 ; i <= _muchii ; ++i)
    {
        int operatie, x, y;
        fin >> operatie >> x >> y;
        int rad_de_x = find_radacina(y, tata);
        int rad_de_y = find_radacina(x, tata);
        if(operatie == 1)
            union_radacini(rad_de_x, rad_de_y, tata);
        else
            if(rad_de_x == rad_de_y)
                gout << "DA" << '\n';
            else
                gout << "NU" << '\n';
    }

}

// metoda aplica algoritmul lui Kruskal si calculam costul_total si returnam lista de muchii a arborelui partial de cost minim
vector<pereche> Graful_meu::Kruskal_Algorithm(int &total_weight)
{
    vector<int>tata(_noduri + 2);
    vector<pair<int, pereche>>lista_muchii;
    vector<pereche>APM;
    total_weight = 0;
    for (int i = 1 ; i <= _noduri ; ++i)
        tata[i] = i;
    for(int i = 1 ; i <= _noduri ; ++i)
        for(auto element : lista_adiacenta[i])
            lista_muchii.push_back({element.second, {i, element.first}});
    sort(lista_muchii.begin(), lista_muchii.end());
    for(auto muchie : lista_muchii)
    {
        int xComponent = find_radacina(muchie.second.first, tata);
        int yComponent = find_radacina(muchie.second.second, tata);
        if(xComponent != yComponent)
        {
            APM.push_back(muchie.second);
            union_radacini(xComponent, yComponent, tata);
            total_weight += muchie.first;
        }
    }
    return APM;

}

// algoritmul lui Dijkstra implementat cu priority queue(heap de minim), va returna vectorul de distante minime
// pentru optimizare (de la 90p la 100p) verificam daca am bagat un nod deja in heap ca sa nu il avem de mai multe ori in heap
// deoarece pentru teste foarte mari este costisitor sa verificam de mai multe ori pentru acelasi nod din heap
// (accesare listei de vecini al aceluiasi nod ar fi redundanta)
vector<int> Graful_meu::Dijkstra_Algorithm()
{
    priority_queue<pereche, vector<pereche>, greater<pereche>> min_heap;
    vector<int> dist_minima(_noduri + 2, INFINIT);
    vector<bool>inMinHeap(_noduri + 2, false);

    min_heap.push({0, 1});
    dist_minima[1] = 0;

    while(!min_heap.empty())
    {
        int nod_curent = min_heap.top().second;
        int distanta_curent = min_heap.top().first;
        min_heap.pop();

        if(inMinHeap[nod_curent] == true)
            continue;

        inMinHeap[nod_curent] = true;
        for(auto vecin : lista_adiacenta[nod_curent])
        {
            int distanta_vecin = vecin.second;
            int nod_vecin = vecin.first;

            if(dist_minima[nod_vecin] > dist_minima[nod_curent] + distanta_vecin)
            {
                dist_minima[nod_vecin] = dist_minima[nod_curent] + distanta_vecin;
                min_heap.push({dist_minima[nod_vecin], nod_vecin});
            }
        }
    }
    for(int i = 2 ; i <= _noduri ; ++i)
        if(dist_minima[i] == INFINIT)
            dist_minima[i] = 0;

    return dist_minima;
}

// algoritmul lui BellMan-Ford care ne va intoarce vectorul de distante, ne vom folosi de un priority queue(heap de minim)
// daca avem un ciclu negativ (adica daca vom avea mai mult de ((n-1) * m) iteratii, idee discutata la curs) vom afisa un mesaj corespunzator
// si vom intoarce un vector gol in acest caz
// am folosit conversia la long long, deoarece produsul ajunge in jur de 10^10
// solutia fara vectorul "ruta_mai_buna" ne ofera 85p (pica un test pe infoarena)
// acest vector de bool ne va ajuta sa nu retinem in heap de mai multe ori acelasi nod (idee aplicata la cateva probleme de mai sus)
vector<int> Graful_meu::Bellman_Ford_Algorithm()
{
    long long numar_iteratii = 0;
    vector<int>dist_minima(_noduri + 2, INFINIT);
    priority_queue<pereche, vector<pereche>, greater<pereche>> min_heap;
    vector<bool>ruta_mai_buna(_noduri + 2, false); // acest vector ne ajuta sa avem o complexitate mai buna

    min_heap.push({0, 1});
    dist_minima[1] = 0;

    while(!min_heap.empty())
    {
        if(numar_iteratii > (long long) (_noduri - 1) * _muchii)      // ciclu negativ maxim aprox 12,5 * 10^9
        {
                gout << "Ciclu negativ!";
                return vector<int>();
        }

        int nod_curent = min_heap.top().second;
        min_heap.pop();

        ruta_mai_buna[nod_curent] = false;
        for(auto vecin : lista_adiacenta[nod_curent])
        {
            int distanta_vecin = vecin.second;
            int nod_vecin = vecin.first;

            if(dist_minima[nod_vecin] > dist_minima[nod_curent] + distanta_vecin)
            {
                dist_minima[nod_vecin] = dist_minima[nod_curent] + distanta_vecin;
                if(ruta_mai_buna[nod_vecin] == false)
                {
                    min_heap.push({dist_minima[nod_vecin], nod_vecin});
                    ruta_mai_buna[nod_vecin] = true;
                }
            }
        }

        ++numar_iteratii;
    }

    return dist_minima;

}

vector<vector<long long>> Graful_meu::Roy_Floyd_Algorithm()
{
    int i, j, k;
    vector<vector<long long>> matrice_ponderi(_noduri + 2, vector<long long>(_noduri + 2));
    for(i = 1; i <= _noduri; ++i)
        for(j = 1; j <= _noduri; ++j)
            {
                fin >> matrice_ponderi[i][j];
                if(matrice_ponderi[i][j] == 0)
                    matrice_ponderi[i][j] = INFINIT;
            }

    for(k = 1; k <= _noduri; ++k)
        for(i = 1; i <= _noduri; ++i)
            for(j = 1; j <= _noduri; ++j)
                    matrice_ponderi[i][j] = min(matrice_ponderi[i][j], matrice_ponderi[i][k] + matrice_ponderi[k][j]);

    for(i = 1; i <= _noduri; ++i)
        for(j = 1; j <= _noduri; ++j)
            if((matrice_ponderi[i][j] == INFINIT) or (i == j))
                matrice_ponderi[i][j] = 0;

    return matrice_ponderi;
}

int Graful_meu::diametru_arbore()
{
    int diametru_maxim, index_max_el;
    vector<int> drumuri_minime_BFS_1 = BFS(1);
    index_max_el = max_element(drumuri_minime_BFS_1.begin(), drumuri_minime_BFS_1.end()) - drumuri_minime_BFS_1.begin();
    vector<int> drumuri_minime_BFS_2 = BFS(index_max_el);
    diametru_maxim = *max_element(drumuri_minime_BFS_2.begin(), drumuri_minime_BFS_2.end()) + 1;

    return diametru_maxim;
}

int Graful_meu::bfs_Edmonds_Karp_Algorithm(int sursa, int destinatie, vector<int> &tata, vector<vector<int>>&capacitate_reziduala)
{
    tata.clear();
    tata.resize(_noduri + 2, NIL);
    tata[sursa] = 0;
    queue<pereche>coada_nod_si_flow;
    coada_nod_si_flow.push({sursa, INFINIT});


    while(!coada_nod_si_flow.empty())
    {
        int nod_curent = coada_nod_si_flow.front().first;
        int flow = coada_nod_si_flow.front().second;
        coada_nod_si_flow.pop();

        for(auto vecin : lista_adiacenta[nod_curent])
        {
            if(tata[vecin.first] == -1 and capacitate_reziduala[nod_curent][vecin.first])
            {
                tata[vecin.first] = nod_curent;
                int new_flow = min(flow, capacitate_reziduala[nod_curent][vecin.first]);
                if(vecin.first == destinatie)
                    return new_flow;
                coada_nod_si_flow.push({vecin.first, new_flow});
            }
        }
    }

    return 0;
}

int Graful_meu::maxFlow_Edmonds_Karp_Algorithm(int sursa, int destinatie)
{
    int total_flow = 0;
    vector<int> tata;
    int new_flow;

    vector<vector<int>>capacitate_reziduala(_noduri + 2, vector<int>(_noduri + 2));
    for(int nod = 1; nod <= _noduri; ++nod)
        for(auto vecin : lista_adiacenta[nod])
            capacitate_reziduala[nod][vecin.first] = vecin.second;

    while(new_flow = bfs_Edmonds_Karp_Algorithm(sursa, destinatie, tata, capacitate_reziduala))
    {
        total_flow += new_flow;
        int nod_curent = destinatie;
        while(nod_curent != sursa)
        {
            int nod_anterior = tata[nod_curent];
            capacitate_reziduala[nod_anterior][nod_curent] -= new_flow;
            capacitate_reziduala[nod_curent][nod_anterior] += new_flow;
            nod_curent = nod_anterior;
        }

    }

    return total_flow;
}

int main()
{
    //citire numar de noduri si numar de muchii(inafara de Havel Hakimi)
    int noduri, muchii;
    fin >> noduri >> muchii;

    // DFS - Componente conexe
/*
    Graful_meu g(noduri, muchii, false);
    g.citire_graf();
    gout << g.Componente_conexe();
*/

    // BFS
/*
    int nod_start, i;
    fin >> nod_start;
    Graful_meu g(noduri, muchii, true);
    g.citire_graf();
    vector<int>drumuri_minime = g.BFS(nod_start);
    for(i = 1; i <= noduri; ++i)
        gout << drumuri_minime[i] << " ";
*/

    // Componente biconexe - Algoritm Tarjan modificat
/*
    Graful_meu g(noduri, muchii, false);
    g.citire_graf();
    vector<vector<int>>toate_componentele_biconexe = g.Componente_Biconexe();
    gout << toate_componentele_biconexe.size() << '\n';
    for(auto &one_biconex_comp : toate_componentele_biconexe)
    {
        for(auto element : one_biconex_comp)
            gout << element << " ";
        gout << '\n';
    }
*/

    // Componente tare conexe - Algoritm Tarjan
/*
    Graful_meu g(noduri, muchii, true);
    g.citire_graf();
    vector<vector<int>>toate_componentele_tare_conexe = g.Componente_Tare_Conexe();
    gout << toate_componentele_tare_conexe.size() << '\n';
    for(auto &one_strongly_connected_comp : toate_componentele_tare_conexe)
    {
        for(auto element : one_strongly_connected_comp)
            gout << element << " ";
        gout << '\n';
    }
*/
    // Critical connections - Algoritm Tarjan - same
/*
    Graful_meu g(noduri, muchii, false);
    g.citire_graf();
    vector<vector<int>>crit_conn = g.criticalConnections();
    gout << crit_conn.size() << '\n';
    for(auto &one_crit_conn : crit_conn)
    {
        for(auto element : one_crit_conn)
            gout << element << " ";
        gout << '\n';
    }
*/
    // Sortare topologica
/*
    Graful_meu g(noduri, muchii, true);
    g.citire_graf();
    vector<int>ordine_topologica = g.TopologicalSort();
    for(auto nod : ordine_topologica)
        gout << nod << " ";
*/
    // Havel Hakimi

/*
    int n;
    fin >> n;
    Graful_meu g(n);
    vector<int>grade(n + 2);
    for(int i = 0; i < n; ++i)
        fin >> grade[i];

    bool formare_graf = g.Havel_Hakimi(n, grade);
    if(formare_graf)
        gout << "Se poate forma graful!";
    else
        gout << "Nu se poate forma graful!";
*/

// APM - Prim's Algorithm
/*
    int cost_total;
    Graful_meu g(noduri, muchii, false, true);
    g.citire_graf();

    vector<int>tata = g.Prim_Algorithm(cost_total);
    gout << cost_total << '\n' << g.getter_numar_noduri() - 1 << '\n';
    for(int i = 2 ; i <= g.getter_numar_noduri(); ++i)
        gout << i << " " << tata[i] << '\n';
*/

// Paduri de multimi disjuncte
/*
    Graful_meu g(noduri, muchii);
    g.paduri_multimi_disjuncte();
*/

// APM - Kruskal's Algorithm
/*
    int cost_total;
    Graful_meu g(noduri, muchii, false, true);
    g.citire_graf();

    vector<pereche>APM = g.Kruskal_Algorithm(cost_total);
    gout << cost_total << '\n' << g.getter_numar_noduri() - 1 << '\n';
    for(auto muchie : APM)
        gout << muchie.first << " " << muchie.second << '\n';
*/

// Drumuri minime - Dijkstra's Algorithm
/*
    Graful_meu g(noduri, muchii, true, true);
    g.citire_graf();

    vector<int> dist_min = g.Dijkstra_Algorithm();
    for(int i = 2 ; i <= g.getter_numar_noduri() ; ++i)
        gout << dist_min[i] << " ";
*/
/*
// Drumuri minime - Bellman-Ford's Algorithm
    Graful_meu g(noduri, muchii, true, true);
    g.citire_graf();

    vector<int> dist_min = g.Bellman_Ford_Algorithm();
    if(dist_min != vector<int>())
        for(int i = 2 ; i <= g.getter_numar_noduri() ; ++i)
            gout << dist_min[i] << " ";
*/

// Algoritmul Roy-Floyd
/*
    Graful_meu g(noduri);
    int l, t;
    vector<vector<long long>> matrice_drumuri_minime = g.Roy_Floyd_Algorithm();
    for(l = 1; l <= noduri; ++l)
    {
        for(t = 1; t <= noduri; ++t)
            gout << matrice_drumuri_minime[l][t] << " ";
        gout << '\n';
    }
*/

// Diametrul unui arbore
/*
    Graful_meu g(noduri, noduri - 1);
    g.citire_graf();

    gout << g.diametru_arbore();
*/

// Max-Flow - Edmonds-Karp Algorithm
    Graful_meu g(noduri, muchii, false, true);
    g.citire_graf();

    gout << g.maxFlow_Edmonds_Karp_Algorithm(1, noduri);
    return 0;
}