#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define INF 0x3f3f3f3f

using namespace std;

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

class Graf
{
    int numar_noduri, numar_muchii;
    vector <vector <int>> lista_adiacenta;

    /// vector folosit pentru problemele "Dijkstra" si "Bellman-Ford"
    vector <vector <pair<int, int>>> lista_adiacenta2;

    /// date folosite pentru problema "APM"
    struct componente_muchie
    {
        int capat_stang, capat_drept, cost;
    };
    vector <componente_muchie> muchii;

    /// date folosite pentru problema "Critical Connections"
    vector <vector <int>> connections;
    vector<vector<int>> x;

public:

    /// functii de citire pentru grafuri orientate si grafuri neorientate
    void citire_graf_orientat(int, int);
    void citire_graf_neorientat(int, int);

    /// functia folosita pentru problema BFS
    void bfs_initializare();
    void bfs(int);

    /// functiile folosite pentru problema DFS
    void dfs_initializare();
    int numar_componente_conexe();
    void dfs(vector <int> &, int nod);

    /// functiile folosite pentru problema CTC
    void ctc_initializare();
    void parcurgere(vector <vector <int>> &);
    void dfs1(int, unordered_map <int, bool>&, vector <int> &);
    void dfs2(int, unordered_map <int, bool>&, vector <int> &, int, vector <vector <int>> &, vector <vector <int>> &);

    /// functiile folosite pentru problema "Flux maxim";
    void citire_flux();
    int max_flow(vector <vector <pair <int, int>>>, int, int, int);
    int bfs_maxflow(int, int, vector <vector <int>>&, vector<int>&, vector <vector <int>>&, vector <int>&, vector <vector<int>>&);

    /// functiile folosite pentru problema "Floyd-Washall/Roy-Floyd"
    void citire_roy_floyd();
    vector <vector <int>> roy_floyd(vector <vector <int>>matrice_ponderi, int cost)
    {
        // complexitate algoritm: O(n^3)
        vector <vector <int>> distante = matrice_ponderi;

        for(int i = 1; i <= numar_noduri; i++)
            for(int j = 1; j <= numar_noduri; j++)
                if(i != j && !matrice_ponderi[i][j])
                    distante[i][j] = cost;      // adaugam in matricea drumurilor minime costurile muchiilor pentru nodurile adiacente

        for(int i = 1; i <= numar_noduri; i++)
            for(int j = 1; j <= numar_noduri; j++)      // incercam sa gasim pentru orice 2 noduri j si k, un nod i pe care daca-l parcurgem, obtinem o distanta mai mica
                for(int k = 1; k <= numar_noduri; k++)  // intre nodurile j si k
                    if(j != k && distante[j][k] > distante[j][i] + distante[i][k])  // verificam daca se indeplineste conditiasi daca j si k sunt acelasi nod
                        distante[j][k] = distante[j][i] + distante[i][k];

        return distante;
    }

    /// functiile folosite pentru problema "Diametrul unui arbore"
    void citire_darb();
    void bfs_darb_init();
    void bfs_darb(int, int &, int &);

    /// functiile folosite pentru problema APM
    void citire();
    void apm();
    int gasire(int, int[]);
    void unire(int, int, int[], int[]);

    /// functiile folosite pentru problema "Paduri de multimi disjuncte"
    void disjoint();
    int gasire_multime(int, int[]);
    void operatie_tip_1(int, int, int[], int[]);

    /// functia folosita pentru Havel-Hakimi
    void havel_hakimi();

    /// functiile folosite pentru problema sortaret
    void sortare_topologica();
    void functie(int nod, int vizitarest[], stack <int> &stiva);

    /// functiile folosite pentru problema biconex
    void dfs_biconex1();
    void dfs_biconex2(int, int, int &, stack <int> &, vector <vector <int>>&, vector <int> &, vector <int> &, vector<int> &);

    /// de aici incep functiile pentru problema "critical connections"
    void citire_leetcode();
    void functie1(vector<int> adiacenta[], vector<vector<int>>& connections)
    {
        for(int i = 0; i < connections.size(); i++)
        {
            adiacenta[connections[i][0]].push_back(connections[i][1]);
            adiacenta[connections[i][1]].push_back(connections[i][0]);
        }
    }

    void dfs_leetcode(vector <int> adiacenta[], int v1[], int v2[], bool vizitare[], int s, int nod, int &numar1)
    {
        vizitare[s] = true;
        v1[s] = v2[s] = ++numar1;

        for(int &i: adiacenta[s])
        {
            if(!vizitare[i])
            {
                dfs_leetcode(adiacenta, v1, v2, vizitare, i, s, numar1);
                v2[s] = min(v2[s], v2[i]);

                if(v2[i] > v1[s])
                    x.push_back({s, i});
            }
            else if(i != nod)
                v2[s] = min(v2[s], v1[i]);
        }
    }
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections)
    {

        vector <int> adiacenta[n];
        functie1(adiacenta, connections);

        int v1[n];
        fill(v1, v1 + n, 0);

        int v2[n];
        fill(v2, v2 + n, 0);

        bool vizitare[n];
        fill(vizitare, vizitare + n, false);

        int numar1 = 0;
        dfs_leetcode(adiacenta, v1, v2, vizitare, 0, -1, numar1);
        return x;
    }
    /// aici se termina functiile pentru problema "critical connections"

    /// pentru problema "Dijkstra"
    void dijkstra1();

    vector <int> dijkstra2(const int a)
    {
        int b;
        vector <int> lungime_drum(numar_noduri + 1, INF);   // aici retinem lungimea drumurilor cautate
        vector <bool> pq(numar_noduri + 1, 0);  // pentru a marca nodurile vizitate
        // priority queue folosit pentru a retine nodul cel mai apropiat
        priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair<int, int>>> coada;

        // lungimea drumul de la nodul de incepere la el insusi este 0
        lungime_drum[a] = 0;
        coada.push(make_pair(0, a));

        // parcurgem elementele priority queue-ului
        while(!coada.empty())
        {
            b = coada.top().second; // cel mai mic nod
            coada.pop();

            // daca nu a fost vizitat
            if(pq[b] == 0)
            {
                pq[b] = 1;  // il marcam ca fiind vizitat
                // ii verificam vecinii
                for(int i = 1; i < lista_adiacenta2[b].size(); i++)
                    // daca distanta pana la nod e mai mare decat lungimea calculata pana la momentul acesta, o modificam
                    if(lungime_drum[lista_adiacenta2[b][i].first] > lungime_drum[b] + lista_adiacenta2[b][i].second)
                {
                    lungime_drum[lista_adiacenta2[b][i].first] = lungime_drum[b] + lista_adiacenta2[b][i].second;
                    coada.push(make_pair(lungime_drum[lista_adiacenta2[b][i].first], lista_adiacenta2[b][i].first));
                }
            }
        }

        return lungime_drum;

    }

    /// pentru problema "Bellman-Ford"
    void bellman_ford1();
    vector <int> bellman_ford2(const int a)
    {
            int ok = 1, b;
            queue <int> coada;
            vector <bool> m(numar_noduri + 1, false);
            vector <int> v(numar_noduri + 1, 0);
            vector <int> distanta(numar_noduri + 1, INF);

            // marcam nodul de la care incepem
            m[a] = 1;
            distanta[a] = 0;
            coada.push(a);

            while(ok && !coada.empty())
            {
                b = coada.front();
                m[b] = 0;
                coada.pop();

                // parcurgem lista de adiacenta a nodului curent
                for(int i = 1; i < lista_adiacenta2[b].size(); i++)
                    // daca avem un cost mai mare decat costul pe care l-am forma cu muchia actuala, il modificam
                    if(distanta[b] + lista_adiacenta2[b][i].second < distanta[lista_adiacenta2[b][i].first])
                {
                    v[lista_adiacenta2[b][i].first]++;
                    distanta[lista_adiacenta2[b][i].first] = distanta[b] + lista_adiacenta2[b][i].second;

                    // daca al doilea nod nu este in queue, il adaugam
                    if(m[lista_adiacenta2[b][i].first] == 0)
                    {
                        coada.push(lista_adiacenta2[b][i].first);
                        m[lista_adiacenta2[b][i].first] = 1;
                    }

                    // daca un nod a fost relaxat de un numar mai mare de ori decat numarul de noduri, inseamna ca exista un ciclu
                    if(v[lista_adiacenta2[b][i].first] >= numar_noduri)
                        ok = 0;

                }
            }

    if(ok == 0)
        distanta.clear();

    return distanta;
    }

};

/// functia de citire pentru grafuri orientate
void Graf :: citire_graf_orientat(int numar_noduri, int numar_muchii)
{
    int capat_stang, capat_drept;
    lista_adiacenta.resize(numar_noduri + 1);

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);
    }
}

/// functia de citire pentru grafuri neorientate
void Graf :: citire_graf_neorientat(int numar_noduri, int numar_muchii)
{
    int capat_stang, capat_drept;
    lista_adiacenta.resize(numar_noduri + 1);

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);
        lista_adiacenta[capat_drept].push_back(capat_stang);
    }
}

/// functii pentru problema "BFS"
void Graf :: bfs_initializare()
{
    int nod_start;

    fin >> numar_noduri >> numar_muchii >> nod_start;

    citire_graf_orientat(numar_noduri, numar_muchii);

    bfs(nod_start);

    lista_adiacenta.clear();
}

/// algoritmul bfs - parcurgerea in latime a unui graf
void Graf :: bfs(int nod_start)
{
    int nod_curent;
    queue <int> coada;
    int vizitare[numar_noduri + 1] = {};

    coada.push(nod_start);  // adaugam in coada nodul de la care se incepe parcurgerea
    vizitare[nod_start] = 1;    // marcam nodul de start ca fiind vizitat

    int cost_nod[numar_noduri + 1] = {};   // pentru retinerea numarului minim de arce ce trebuie parcurse
    cost_nod[nod_start] = 0;

    while(coada.size() > 0)
    {
        nod_curent = coada.front();

        for(int i = 0; i < lista_adiacenta[nod_curent].size(); i++)
            if(!vizitare[lista_adiacenta[nod_curent][i]])   // daca un nod adiacent cu nodul curent nu este vizitat se executa codul de mai jos
        {
            coada.push(lista_adiacenta[nod_curent][i]); // adaugam in queue nodurile nevizitate
            cost_nod[lista_adiacenta[nod_curent][i]] = cost_nod[nod_curent] + 1;
            vizitare[lista_adiacenta[nod_curent][i]] = 1;   // le marcam ca fiind vizitate
        }
        coada.pop();    // scoatem din coada nodul curent
    }

    for(int i = 1; i <= numar_noduri; i++)
        if(vizitare[i])
            fout << cost_nod[i] << " "; // afisam numarul minim de arce ce trebuie parcurse de la nodul de start la nodul i
        else
            fout << "-1 ";  // afisam -1 pentru nodurile la care nu se poate ajunge din nodul de start

}

/// functii folosite pentru problema "DFS"
void Graf :: dfs_initializare()
{
    fin >> numar_noduri >> numar_muchii;

    citire_graf_neorientat(numar_noduri, numar_muchii);

    fout << numar_componente_conexe();

    lista_adiacenta.clear();
}

/// functia pentru numararea componentelor conexe
int Graf :: numar_componente_conexe()
{
    int numar_componente = 0;
    vector <int> vizitare;

    for(int i = 1; i <= numar_noduri + 1; i++)
        vizitare.push_back(0);      // vector folosit pentru a sti daca un nod a fost sau nu vizitat

    for(int i = 1; i <= numar_noduri; i++)
        if(!vizitare[i])    // daca nodul a fost vizitat, inseamna ca apartine unei componente conexe numarate deja
    {
        dfs(vizitare, i);   // numarul de componente conexe este egal cu numarul de apeluri ale functiei dfs din interiorul functiei numar_componente_conexe
        numar_componente++;
    }
    return numar_componente;
}

/// algoritmul dfs - parcurgerea in adancime a grafului
void Graf :: dfs(vector <int> &vizitare, int nod)
{
    vizitare[nod] = 1;  // marcam nodul curent ca fiind vizitat

    for(int i = 0; i < lista_adiacenta[nod].size(); i++)
        if(!vizitare[lista_adiacenta[nod][i]])
            dfs(vizitare, lista_adiacenta[nod][i]);    // apelam in mod recursiv functia dfs pentru a parcurge toate nodurile dintr-o componenta conexa

}

/// functii folosite pentru problema "CTC"
void Graf :: ctc_initializare()
{
    int capat_stang, capat_drept;
    vector <vector <int>> lista_adiacenta1;

    lista_adiacenta.resize(numar_noduri + 1);
    lista_adiacenta1.resize(numar_noduri + 1);

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);    // listele de adiacenta pentru graful dat
        lista_adiacenta1[capat_drept].push_back(capat_stang);   // listele de adiacenta pentru graful transpus
    }

    parcurgere(lista_adiacenta1);

    lista_adiacenta.clear();
    lista_adiacenta1.clear();
}


/// pentru problema CTC pentru rezolvarea careia s-a folosit algoritmul lui Kosaraju
void Graf :: parcurgere(vector <vector <int>> &lista_adiacenta1)
{
    int numar_componente = 0;
    vector <int> st;    // vectorul in care vom stoca nodurile
    vector < vector <int>> componenta;
    unordered_map <int, bool> vizitare1, vizitare2;

    for(int i = 1; i <= numar_noduri; i++)
        if(!vizitare1[i])
            dfs1(i, vizitare1, st);     // realizam o parcurgere in adancime a grafului dat

    for(int i = st.size() - 1; i >= 0; i--)
        if(!vizitare2[st[i]])   // pornind de la ultimul nod adaugat in vector, realizam parcurgerea in adancime a grafului transpus
    {
        dfs2(st[i], vizitare2, st, numar_componente, componenta, lista_adiacenta1);
        numar_componente++;     // numarul de componente conexe tare este egal cu numarul de apeluri ale functiei de parcurgere in adancime a grafului transpus
    }

    // afisarea rezultatului
    fout << numar_componente << '\n';

    for(int i = 0; i < numar_componente; i++)
    {
        for(int j = 0; j < componenta[i].size(); j++)
            fout << componenta[i][j] << " ";

        fout << '\n';
    }
}

/// primul algoritm DFS pentru problema CTC
void Graf :: dfs1(int nod, unordered_map <int, bool> &vizitare1, vector <int> &st)
{
    vizitare1[nod] = true;  // marcam nodul curent ca fiind vizitat

    for(int i = 0; i < lista_adiacenta[nod].size(); i++)
        if(!vizitare1[lista_adiacenta[nod][i]])
            dfs1(lista_adiacenta[nod][i], vizitare1, st);   // apelam in mod recursiv primul algoritm DFS pentru graful dat

    st.push_back(nod);      // introducem in vector nodurile in ordinea inversa fata de cea in care au fost vizitate
}

/// al doilea algoritm DFS pentru problema CTC
void Graf :: dfs2(int nod, unordered_map <int, bool> &vizitare2, vector <int> &st, int numar_componente, vector <vector <int>> &componenta, vector <vector <int>> &lista_adiacenta1)
{
    vizitare2[nod] = true;
    componenta.resize(numar_componente + 1);
    componenta[numar_componente].push_back(nod);    // adaugam in fiecare componenta tare conexa nodurile corespunzatoare

    for(int i = 0; i < lista_adiacenta1[nod].size(); i++)
        if(!vizitare2[lista_adiacenta1[nod][i]])
            dfs2(lista_adiacenta1[nod][i], vizitare2, st, numar_componente, componenta, lista_adiacenta1);    // apelam in mod recursiv al doilea algoritm DFS pentru graful transpus
}


/// functii folosite pentru problema "Flux maxim"
int Graf :: bfs_maxflow(int sursa, int destinatie, vector <vector <int>>& capacitati, vector <int> &tata, vector <vector <int>>&flux, vector <int> &vizitat, vector <vector<int>>&rezidual)
{
    int a;
    queue <int> coada;
    coada.push(sursa);

    tata.assign(capacitati.size(), 0);
    tata[sursa] = -1;

    vizitat.clear();
    vizitat.resize(capacitati.size(), 0);

    vizitat[sursa] = 1;

    while(!tata[destinatie] && !coada.empty())
    {
        a = coada.front();
        coada.pop();

        for(int i : rezidual[a])
            if(capacitati[a][i] > flux[a][i] && !vizitat[i])
        {
            tata[i] = a;
            vizitat[i] = 1;
            coada.push(i);
        }

    }
    return tata[destinatie];

}


int Graf :: max_flow(vector <vector <pair <int, int>>> lista_adiacenta, int sursa, int destinatie, int capacitate_maxima)
{
    int maxim = 0, flux_drum, a;
    vector <int> vizitat(numar_noduri + 1, 0);
    vector <int> tata(numar_noduri + 1, 0);
    vector <vector <int>> rezidual(numar_noduri + 1);
    vector <vector <int>> capacitati(numar_noduri + 1, vector <int>(numar_noduri + 1, 0));
    vector <vector <int>> flux(numar_noduri + 1, vector <int>(numar_noduri + 1, 0));

    for(int i = 0; i < numar_noduri + 1; i++)
        for(int j = 0; j < lista_adiacenta[i].size(); j++)
    {
        capacitati[i][lista_adiacenta[i][j].first] = lista_adiacenta[i][j].second;
        rezidual[i].push_back(lista_adiacenta[i][j].first);
        rezidual[lista_adiacenta[i][j].first].push_back(i);
    }

    while(bfs_maxflow(sursa, destinatie, capacitati, tata, flux, vizitat, rezidual))
    {
        for(int i : rezidual[destinatie])
            if(flux[i][destinatie] < capacitati[i][destinatie] && vizitat[i])
        {
            flux_drum = capacitate_maxima;
            tata[destinatie] = i;

            for(int j = destinatie; j != sursa; j = tata[j])
            {
                a = tata[j];

                if(flux_drum > capacitati[a][j] - flux[a][j])
                    flux_drum = capacitati[a][j] - flux[a][j];
            }
            if(flux_drum)
            {
                for(int j = destinatie; j != sursa; j = tata[j])
            {
                a = tata[j];
                flux[a][j] += flux_drum;
                flux[j][a] -= flux_drum;
            }

            maxim += flux_drum;
            }

        }
    }

    return maxim;
}


void Graf :: citire_flux()
{
    int nod1, nod2, capacitate;

    fin >> numar_noduri >> numar_muchii;

    vector <vector <pair <int, int>>> lista_adiacenta;
    lista_adiacenta.resize(numar_noduri + 1);

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> nod1 >> nod2 >> capacitate;
        lista_adiacenta[nod1].push_back(make_pair(nod2, capacitate));
    }

    fout << max_flow(lista_adiacenta, 1, numar_noduri, 110001);
}


/// functie folosita pentru problema "Roy-Floyd"
void Graf :: citire_roy_floyd()
{
    // citire date
    fin >> numar_noduri;

    vector <vector <int>> matrice_ponderi;
    matrice_ponderi.resize(numar_noduri + 1);

    for(int i = 1; i <= numar_noduri; i++)
    {
        matrice_ponderi[i].resize(numar_noduri + 1);
        for(int j = 1; j <= numar_noduri; j++)
            fin >> matrice_ponderi[i][j];
    }

    // in matricea distante vom retine matricea drumurilor minime
    vector <vector <int>> distante = roy_floyd(matrice_ponderi, 1001);

    // afisare rezultat
    for(int i = 1; i <= numar_noduri; i++)
    {
        for(int j = 1; j <= numar_noduri; j++)
            fout << distante[i][j] << " ";
        fout << '\n';
    }
}


void Graf :: bellman_ford1()
{
    int nod1, nod2, cost;
    vector <pair <int, int>> x(1, make_pair(-1, -1));

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i <= numar_noduri + 1; i++)
        lista_adiacenta2.push_back(x);

    // citire date
    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> nod1 >> nod2 >> cost;
        lista_adiacenta2[nod1].push_back(make_pair(nod2, cost));
    }

    // retinem in vectorul distanta rezultatul
    vector <int> distanta = bellman_ford2(1);

    // afisarea rezultatului
    if(!distanta.size())
        fout << "Ciclu negativ!";
    else for(int i = 2; i <= numar_noduri; i++)
        fout << distanta[i] << " ";
}

/// functia de citire pentru problema "critical connections"
void Graf :: citire_leetcode()
{
    int n, x, y;
    fin >> n;

    for(int i = 0; i < n; i++)
    {
        fin >> x >> y;
        connections.push_back({x, y});
    }

    vector <vector <int>> rezultat = criticalConnections(n, connections);

    for(int i = 0; i < rezultat.size(); i++)
    {
        for(int j = 0; j < rezultat[i].size(); j++)
            fout << rezultat[i][j] << " ";
        fout << '\n';
    }
}

/// pentru problema Dijkstra
void Graf :: dijkstra1()
{
    int nod1, nod2, lungime_arc;
    vector <pair <int, int>> lista(1, make_pair(-1, -1));

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i <= numar_noduri + 1; i++)
        lista_adiacenta2.push_back(lista);

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> nod1 >> nod2 >> lungime_arc;
        lista_adiacenta2[nod1].push_back(make_pair(nod2, lungime_arc));
    }

    // in acest vector am stocat rezultatul
    vector <int> lungime_drum = dijkstra2(1);

    // afisarea rezultatului
    for(int i = 2; i <= numar_noduri; i++)
        if(lungime_drum[i] != INF)
            fout << lungime_drum[i] << " ";
        else
            fout << 0 << " ";
}

/// functia de citire pentru problema APM
void Graf :: citire()
{
    int capat_stang, capat_drept, cost;

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept >> cost;
        muchii.push_back({capat_stang, capat_drept, cost});
    }
}

int Graf :: gasire(int a, int noduri1[])
{
    int aux = a, aux2;

    while(noduri1[aux] != aux)
    {
        aux = noduri1[aux];
    }

    while(a != aux)
    {
        aux2 = noduri1[a];
        noduri1[a] = aux;
        a = aux2;
    }

    return a;
}

void Graf :: unire(int a, int b, int noduri1[], int noduri2[])
{
    a = gasire(a, noduri1);
    b = gasire(b, noduri1);

    if(noduri2[a] < noduri2[b])
        noduri1[a] = b;
    else
    {
        noduri1[b] = a;
        if(noduri2[a] == noduri2[b]) noduri2[a]++;
    }
}

void Graf :: apm()
{
    int numar_muchii_selectate = 0;
    int cost_minim = 0;
    int noduri1[numar_noduri + 1], noduri2[numar_noduri + 1];

    for(int i = 1; i <= numar_noduri; i++)
        noduri1[i] = i;

    // sortam muchiile dupa cost
    sort(muchii.begin(), muchii.end(), [](const componente_muchie &x, const componente_muchie &y) {return x.cost < y.cost;});

    vector <pair <int, int>> rezultat;

    for(const componente_muchie& x : muchii)
    {
        if(numar_muchii_selectate == numar_noduri - 1)
            break;

        if(gasire(x.capat_stang, noduri1) == gasire(x.capat_drept, noduri1))
            continue;

        numar_muchii_selectate++;
        cost_minim += x.cost;

        unire(x.capat_stang, x.capat_drept, noduri1, noduri2);
        rezultat.push_back({x.capat_stang, x.capat_drept});
    }

    fout << cost_minim << '\n';
    fout << rezultat.size() << '\n';

    for(auto x : rezultat)
        fout << x.second << " " << x.first << '\n';
}

int Graf :: gasire_multime(int a, int parinte[])
{
    while(a != parinte[a])
        a = parinte[a];     // cautam radacina arborelui din care face parte nodul a

    return a;
}

void Graf :: operatie_tip_1(int a, int b, int dimensiune[], int parinte[])
{
    a = gasire_multime(a, parinte);
    b = gasire_multime(b, parinte);

    // unim arborii in functie de rang
    if(dimensiune[b] <= dimensiune[a])
    {
        dimensiune[a] += dimensiune[b];
        parinte[b] = a;
    }
    else
    {
        dimensiune[b] += dimensiune[a];
        parinte[a] = b;
    }
}

/// functia pentru "Paduri de multimi disjuncte"
void Graf :: disjoint()
{
    int numar_multimi, numar_operatii, numar1, numar2, tip_operatie;
    int parinte[1001], dimensiune[1001];

    fin >> numar_multimi >> numar_operatii;

    for(int i = 0; i < numar_multimi; i++)
    {
        dimensiune[i] = 1;  // rangul fiecarui nod este 1 initial
        parinte[i] = i; // tinem minte tatii
    }

    // executam fiecare operatie in parte pe masura ce citim datele
    for(int i = 0; i < numar_operatii; i++)
    {
        fin >> tip_operatie >> numar1 >> numar2;

        if(tip_operatie == 1)
            // unim radacinile arborilor corespunzatori multimilor celor 2 noduri
            operatie_tip_1(numar1, numar2, dimensiune, parinte);

            // verific daca radacina arborilor in care se afla cele 2 noduri este aceeasi
        else if(gasire_multime(numar1, parinte) == gasire_multime(numar2, parinte))
                    fout << "DA" << '\n';
        else fout << "NU" << '\n';
    }
}

/// Havel-Hakimi
void Graf :: havel_hakimi()
{
    int ok = 1, nod, numar_havel;
    vector <int> grade;

    fin >> numar_havel;

    // citim lista de numere pe care le introducem intr-o coada
    while(numar_havel)
    {
        fin >> nod;
        grade.push_back(nod);
        numar_havel--;
    }

    while(true)
    {
        sort(grade.begin(), grade.end(), greater<>());  // sortam lista de grade pentru ca gradul cel mai mare sa fie primul

        // daca cel mai mare grad din lista este 0, atunci putem construi un graf
        if(!grade[0])
            break;

        int x = grade[0];
        grade.erase(grade.begin()); // conform algoritmului Havel-Hakimi, eliminam primul element din lista

        // daca cel mai mare grad al unui nod este mai mare decat numarul de elemente ramase in lista, adica de noduri, inseamna ca nu putem construi un graf
        // pentru ca nodul cu gradul cel mai mare nu ar avea un numar suficient de noduri cu care sa se conecteze
        if(grade.size() < x)
        {
            ok = 0;
            break;
        }

        for(int i = 0; i < x; i++)
        {
            grade[i]--;     // conform algoritmului, "eliminam" muchiile incidente cu nodul eliminat scazand cu 1 din gradele urmatoarelor x noduri

            if(grade[i] < 0)    // daca intalnim un nod cu un grad negativ, nu putem construi un graf
            {
                ok = 0;
                break;
            }
        }

        if(ok == 0)     // conditie pusa pentru iesirea din while pentru cazul in care ok ar fi devenit 0 in cadrul structurii repetitive for
            break;
    }

    if(ok)      // daca ok nu a devenit 0 in timpul structurii repetitive while, atunci inseamna ca putem construi un graf
        fout << "Da";
    else
        fout << "Nu";

}

/// pentru sortarea topologica
void Graf :: sortare_topologica()
{
    stack <int> stiva;  // stiva in care stocam nodurile sortate invers topologic
    int vizitare[numar_noduri + 1] = {};

    for(int i = 1; i <= numar_noduri; i++)
        if(!vizitare[i])
            functie(i, vizitare, stiva);    // folosim algoritmul DFS pentru fiecare componenta conexa a grafului

    // afisam nodurile sortate topologic
    while(!stiva.empty())
    {
        fout << stiva.top() << " ";
        stiva.pop();
    }
}

/// apartine problemei "sortaret" - algoritm DFS
void Graf :: functie(int nod, int vizitare[], stack <int> &stiva)
{
    vizitare[nod] = 1;  // marcam nodul curent ca fiind vizitat

    for(int i = 0; i < lista_adiacenta[nod].size(); i++)
        if(!vizitare[lista_adiacenta[nod][i]])
            functie(lista_adiacenta[nod][i], vizitare, stiva);  // apelam in mod recursiv functia pentru a parcurge toate nodurile nevizitate
                                                                // dintr-o componenta conexa
    stiva.push(nod);    // dupa ce am vizitat toate nodurile care depind de nodul curent, adaugam nodul curent in stiva
}
/*
/// pentru problema biconex
void Graf :: dfs_biconex1()
{
    int numar = 0;      // numarul de componente biconexe
    stack <int> st;
    vector <int> nivel1(numar_noduri + 1);
    vector <int> nivel2(numar_noduri + 1);
    vector <int> nivel3(numar_noduri + 1);
    vector <vector <int>> componente_biconexe(numar_noduri + 1);

    dfs_biconex2(1, 0, numar, st, componente_biconexe, nivel1, nivel2, nivel3);

    // afisarea rezultatului
    fout << numar << '\n';

    for(int i = 0; i < numar; i++)
    {
        for(int j = 0; j < componente_biconexe[i].size(); j++)
            fout << componente_biconexe[i][j] << " ";
        fout << '\n';
    }
}*/
/*
void Graf :: dfs_biconex2(int x, int parinte, int &numar, stack <int> &st, vector <vector <int>>& componente_biconexe, vector <int> &nivel1, vector <int> &nivel2, vector <int> &nivel3)
{
        st.push(x);
        nivel2[x] = nivel2[parinte] + 1;
        nivel1[x] = nivel2[x];
        nivel3[x] = 1;

        for(int i = 0; i < lista_adiacenta1[x].size(); i++)
        {
            int y = lista_adiacenta1[x][i];

            if(parinte != y)
                if(nivel3[y] == 1)
            {
                if(nivel1[x] > nivel2[y])
                    nivel1[x] = nivel1[y];
            }
            else
            {
                dfs_biconex2(lista_adiacenta1[x][i], x, numar, st, componente_biconexe, nivel1, nivel2, nivel3);
                if(nivel1[x] > nivel1[y])
                    nivel1[x] = nivel1[lista_adiacenta1[x][i]];
                if(nivel2[x] <= nivel1[y])
                {
                    while(st.top() != y)
                    {
                        componente_biconexe[numar].push_back(st.top());
                        st.pop();
                    }

                    componente_biconexe[numar].push_back(y);
                    componente_biconexe[numar].push_back(x);
                    st.pop();
                    numar++;
                }
            }
        }
}
*/
/// pentru problema "Diametrul unui arbore"
void Graf :: citire_darb()
{
    int capat_stang, capat_drept;

    fin >> numar_noduri;

    for(int i = 0; i <= numar_noduri; i++)
        lista_adiacenta[i].push_back(-1);

    for(int i = 0; i < numar_noduri - 1; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);
        lista_adiacenta[capat_drept].push_back(capat_stang);
    }
}

void Graf :: bfs_darb_init()
{
    int distanta, nod1, nod2;

    // realizam 2 parcurgeri in latime pornind prima parcurgere de la primul nod si continuand cu a doua din ultimul nod in care am ajuns
    // cea mai indepartata frunza din prima parcurgere reprezinta un capat al lantului
    // urmand sa ii gasim celalalt capat in ultimul nod in care ajungem cu cea de a doua parcurgere
    bfs_darb(1, nod1, distanta);
    bfs_darb(nod1, nod2, distanta);

    fout << distanta;
}

/// algoritm BFS pentru gasirea diametrului unui arbore
void Graf :: bfs_darb(int s, int &u, int &d)
{
    int a;
    int vizitat[numar_noduri + 1] = {};
    int dist[numar_noduri + 1] = {};
    queue <int> coada;

    d = 0;      // in d retinem distanta maxima pentru a putea gasi cel mai indepartat nod
    dist[s] = 1;    // numaram nodurile distanta
    vizitat[s] = 1;     // marcam nodul de start ca fiind vizitat
    coada.push(s);  // adaugam in coada nodul de la care se porneste parcurgerea

    while(!coada.empty())
    {
        a = coada.front();
        coada.pop();

        for(int i = 1; i < lista_adiacenta[a].size(); i++)
            if(vizitat[lista_adiacenta[a][i]] == 0) // daca un nod adiacent cu nodul curent nu este vizitat, il adaugam in coada
        {
            vizitat[lista_adiacenta[a][i]] = 1;     // il marcam ca fiind vizitat
            coada.push(lista_adiacenta[a][i]);      // il adaugam in coada
            dist[lista_adiacenta[a][i]] = dist[a] + 1;  // incrementam cu 1 pentru a masura distanta de la nodul la care ne aflam la nodul adiacent curent
        }
    }

    // la final, aflam care este cel mai indepartat nod de nodul de la care am pornit parcurgerea
    for(int i = 1; i <= numar_noduri; i++)
        if(d < dist[i])
        {
            u = i;
            d = dist[i];
        }
}


int main()
{
    Graf x;
   // fout << "Output pentru problema \"BFS\": ";
    x.dfs_initializare();
/*
    fout << "\nOutput-ul pentru problema \"DFS\": ";
    x.dfs_initializare();

    Graf y;
    fout << "\nOutputul pentru problema \"Componente tare conexe\" este:\n";
    y.ctc_initializare();

    Graf c;
    c.citire_ctc();
    fout << "\nOutputul pentru problema \"Componente tare conexe\" este:\n";
    c.parcurgere();

    Graf z;
    fout << "Output-ul pentru \"Havel-Hakimi\": ";
    z.havel_hakimi();

    Graf t;
    fout << "\nOutput-ul pentru problema \"Sortare topologica\" este: ";
    t.citire_graf_orientat(false);
    t.sortare_topologica();

    Graf g;
    g.citire_graf_neorientat();
    fout << "\nOutput-ul pentru problema \"Componente biconexe\" este:\n";
    g.dfs_biconex1();

    Graf l;
    fout << "Output-ul pentru problema \"Critical Connections in a Network\": ";
    l.citire_leetcode();

    Graf p;
    fout << "Output-ul pentru problema \"Arbore partial de cost minim\" este:\n";
    p.citire();
    p.apm();

    Graf q;
    fout << "Output-ul pentru problema \"Paduri de multimi disjuncte\" este:\n";
    q.disjoint();

    Graf j;
    fout << "Output-ul pentru problema \"Algoritmul lui Dijkstra\" este: ";
    j.dijkstra1();

    Graf h;
    fout << "\nOutput-ul pentru problema \"Algoritmul Bellman-Ford\" este: ";
    h.bellman_ford1();

    Graf k;
    fout << "\nOutput-ul pentru problema \"Diametrul unui arbore\" este: ";
    k.citire_darb();
    k.bfs_darb_init();

    Graf a;
    fout << "\nOutput-ul pentru problema \"Floyd-Washall/Roy-Floyd\" este:\n";
    a.citire_roy_floyd();

    Graf b;
    fout << "Output-ul pentru problema \"Flux maxim\" este: ";
    b.citire_flux();
*/
    fin.close();
    fout.close();

    return 0;
}