#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
#include <climits>
using namespace std;

class Graf
{
   protected:
       int nrNoduri, nrMuchii; ///Numar noduri, numar muchii
       vector <vector <int>> listaAdiacenta; ///lista de adiacenta graf
   public:
       Graf(int const, int const, vector <vector<int>>);
       Graf();
       Graf(const Graf &graf);
       ~Graf();
       int get_noduri() const;
       int get_muchii() const;
       vector <vector<int>> get_lista() const;

       vector <int> BFS(int); ///returneaza vector de distante minime, plecand din nodul de start

       int nr_componente_conexe();

       vector <int> sortareTopologica(vector <int>); ///returneaza sortarea topologica, primind argument un vector de grade interne

       bool HavelHakimi(vector <int> &, int); ///false - nu exista graf / true - exista graf

       vector <vector <int>> CTC(vector <vector<int>>); ///returneaza componentele tare conexe, primind argument lista de adiacenta a grafului transpus

       vector <pair <int, int>> muchiiCritice(); ///returneaza vector cu muchiile critice dintr-un graf

       ///Paduri de multimi disjuncte
       int Find(int, vector <int>); ///gaseste tatal unui nod
       void Union(int, int, vector <int> &, vector <int> &); ///uneste doua noduri

       vector <vector <long long>> royFloyd(vector <vector <long long>>);

       int diametruArbore();

       int fluxMaxim();

    private:
       void DFS(int, vector <int> &);

       void DFS_MuchiiCritice(int, int, vector <int> &, vector <int> &, vector <int> &, vector <pair <int, int>> &);

       void DFS1_CTC_Kosaraju(int, vector <int> &, stack <int>&); ///primul DFS pe graf
       void DFS2_CTC_Kosaraju(int, vector <int> &, vector <vector<int>>, vector <int> &); ///al doilea DFS pe graful transpus

       bool bfsFlux(vector <int> &, vector <vector <int>> &); ///bfs pentru problema flux maxim
};

Graf :: Graf(int const nrNodurioduri, int const nrMuchiiuchii, vector <vector<int>> lista)
{
     nrNoduri = nrNodurioduri;
     nrMuchii = nrMuchiiuchii;
     listaAdiacenta = lista;
}

Graf :: Graf()
{
    nrNoduri = 0;
    nrMuchii = 0;
    vector <vector <int>> lista(nrNoduri + 1);
    listaAdiacenta = lista;
}

Graf :: Graf(const Graf & graf)
{
     nrNoduri = graf.nrNoduri;
     nrMuchii = graf.nrMuchii;
     listaAdiacenta = graf.listaAdiacenta;
}

Graf :: ~Graf()
{
    nrNoduri = 0;
    nrMuchii = 0;
    listaAdiacenta.clear();
}

int Graf :: get_noduri() const
{
    return nrNoduri;
}

int Graf :: get_muchii() const
{
    return nrMuchii;
}

vector <vector<int>> Graf :: get_lista() const
{
    return listaAdiacenta;
}

///BFS - O(N + M)
vector <int> Graf :: BFS(int start)
{
    vector <int> cost(nrNoduri + 1, -1);
    int S;
    queue <int> coada;
    coada.push(start); ///adaugam in coada nodul de start
    cost[start] = 0; ///costul pentru nodul de start este 0
    while (!coada.empty()) ///cat timp avem elemente in coada
    {
        S = coada.front();
        for (int i = 0; i < listaAdiacenta[S].size(); i++) ///parcurgem vecinii nodului curent
        {
            int nod_curent = listaAdiacenta[S][i];
            if (cost[nod_curent] == -1) ///daca e nevizitat
            {
                cost[nod_curent] = cost[S] + 1; ///actualizam costul
                coada.push(nod_curent); ///adaugam in coada vecinul
            }
        }
        coada.pop(); ///eliminam nodul curent din coada
    }
    return cost;
}

///DFS - O(N + M)
void Graf :: DFS(int nod, vector <int> &viz)
{
    viz[nod] = 1; ///vizitam nodul curent
    for (int i = 0; i < listaAdiacenta[nod].size(); i++) ///parcurgem vecinii nodului curent
    {
        int nod_curent = listaAdiacenta[nod][i];
        if (viz[nod_curent] == 0) ///daca vecinul este nevizitat
            DFS(nod_curent, viz);
    }
}

int Graf :: nr_componente_conexe()
{
    vector <int> viz(nrNoduri + 1, 0); ///initializam vectorul viz
    int nrCC = 0; ///numar componente conexe
    for (int i = 1; i <= nrNoduri; i++)
    {
        if (viz[i] == 0) ///daca nodul este nevizitat
        {
            DFS(i, viz);
            nrCC ++;
        }
    }
    return nrCC;
}

///SortareTopologica - O(N + M)
vector <int> Graf :: sortareTopologica(vector <int> grade)
{
    queue <int> coada;
    vector <int> rez;
    for (int i = 1; i <= nrNoduri; i++)
        if (grade[i] == 0)
            coada.push(i); ///adaugam in coada nodurile cu gradul intern 0
    while (!coada.empty())
    {
        int nod_curent = coada.front();
        rez.push_back(nod_curent);
        coada.pop();
        for (int i = 0; i < listaAdiacenta[nod_curent].size(); i++) ///parcurgem vecinii
        {
            int vecin = listaAdiacenta[nod_curent][i];
            grade[vecin]--; ///scadem 1 tuturor gradelor nodurilor adiacente
            if (grade[vecin] == 0) ///daca gradul intern a devenit 0, il adaugam in coada
                coada.push(vecin);
        }
    }
    return rez;
}

///HavelHakimi - O(N^2logN)
bool Graf :: HavelHakimi(vector <int> &v, int n)
{
    bool ok = true;
    while (ok == true)
    {
        sort(v.begin(), v.end(), greater<int>()); ///sortam descrescator gradele nodurilor
        if (v[0] == 0) ///daca toate gradele sunt egale cu 0 - primul element 0 in ordine descrescatoare
            break; ///exista graf
        int nr = v[0]; ///extragem primul grad
        v.erase(v.begin());
        if (nr > v.size()) ///daca gradul este mai mare decat numarul de elemente ramase
         {
            ok = false; ///nu exista graf
            break;
         }
        for (int i = 0; i < nr; i++) ///parcurgem urmatoarele nr elemente
        {
            v[i] = v[i] - 1; ///scadem 1 din grad
            if (v[i] < 0) ///daca gradul a devenit -1
                {
                    ok = false; ///nu exista graf
                    break;
                }
        }
    }
    return ok;
}

///Ctc - O(N + M)
void Graf :: DFS1_CTC_Kosaraju(int nod, vector <int> &vizitat, stack <int> &stiva)
{
    vizitat[nod] = 1;
    for (int i = 0; i < listaAdiacenta[nod].size(); i++)
    {
        int nod_curent = listaAdiacenta[nod][i];
        if (vizitat[nod_curent] == 0)
            DFS1_CTC_Kosaraju(nod_curent, vizitat, stiva);
    }
   stiva.push(nod); ///adaugam in stiva nodurile
}

void Graf :: DFS2_CTC_Kosaraju(int nod, vector <int> &vizitatTr, vector <vector<int>> listaTr, vector <int> &vector_aux)
{
    vector_aux.push_back(nod); ///adaugam nodul la componenta curenta
    vizitatTr[nod] = 1;
    for (int i = 0; i < listaTr[nod].size(); i++)
    {
        int nod_curent = listaTr[nod][i];
        if (vizitatTr[nod_curent] == 0)
            DFS2_CTC_Kosaraju(nod_curent, vizitatTr, listaTr, vector_aux);
    }
}

vector <vector <int>> Graf :: CTC(vector <vector<int>> listaTr)
{
    vector <int> vizitat(nrNoduri + 1, 0);
    vector <int> vizitatTr(nrNoduri + 1, 0);
    stack <int> stiva;
    vector <vector<int>> rez(nrNoduri + 1);
    int nr = 0;
    for (int i = 1; i <= nrNoduri; i++)
        if (vizitat[i] == 0)
            DFS1_CTC_Kosaraju(i, vizitat, stiva); ///primul dfs
    while (!stiva.empty()) ///parcurgem stiva
    {
       int v = stiva.top();
       stiva.pop();
       if (vizitatTr[v] == 0) ///daca nodul curent din stiva e nevizitat
       {
          vector <int> vector_aux;
          DFS2_CTC_Kosaraju(v, vizitatTr, listaTr, vector_aux); ///al doilea dfs
          rez.push_back(vector_aux); ///adaugam la solutie componenta curenta
          nr++; ///incrementam numarul de componente
       }
    }
    return rez;
}

///MuchiiCritice - O(N + M)
vector <pair <int, int>> Graf :: muchiiCritice()
{
    vector <int> vizitat(nrNoduri + 1, 0);
    vector <int> nivel(nrNoduri + 1, 0);
    vector <int>nivelInt(nrNoduri + 1, 0);
    vector <pair <int, int>> rez;
    DFS_MuchiiCritice(0, 0, vizitat, nivel, nivelInt, rez);
    return rez;
}

void Graf :: DFS_MuchiiCritice(int nod, int tata, vector <int> &vizitat, vector <int> &nivel, vector <int> &nivelInt,
                              vector <pair <int, int>> &rez )
{
    vizitat[nod] = 1;
    nivel[nod] = nivel[tata] + 1; ///actualizam nivelul
    nivelInt[nod] = nivel[nod]; ///actualizam nivelul de intoarcere
    for (int i = 0; i < listaAdiacenta[nod].size(); i++)
    {
        int copil = listaAdiacenta[nod][i];
        if (copil != tata)
        {
            if (vizitat[copil] == 1)
                {
                    if (nivelInt[nod] > nivel[copil]) ///actualizam nivelul de intoarcere acolo unde gasim o muchie de intoarcere
                       nivelInt[nod] = nivel[copil];
                }
            else
            {
                DFS_MuchiiCritice(copil, nod, vizitat, nivel, nivelInt, rez);
                if (nivelInt[nod] > nivelInt[copil]) ///actualizam nivelul de intoarcere in cazul in care un copil are acest nivel mai mic
                    nivelInt[nod] = nivelInt[copil];
                if (nivel[nod] < nivelInt[copil]) ///conditie muchii critice
                    rez.push_back(make_pair(nod, copil));
            }
        }
    }

}

///PaduriDeMultimiDisjuncte
///O(logN)
int Graf :: Find(int nod, vector <int> tata)
{
    if (tata[nod] == nod)
          return nod;
    return Find(tata[nod], tata);
}

///O(1)
void Graf :: Union(int nod1, int nod2, vector <int> &tata, vector <int> &rang)
{
    int TataNod1 = Find(nod1, tata);
    int TataNod2 = Find(nod2, tata);
    if (TataNod1 == TataNod2)
        return;
    if (rang[TataNod1] < rang[TataNod2])
           tata[TataNod1] = TataNod2;
    else if (rang[TataNod1] > rang[TataNod2])
             tata[TataNod2] = TataNod1;
         else
         {
            tata[TataNod2] = TataNod1;
            rang[TataNod1]++;
         }
}

///RoyFloyd - O(N^3)
vector <vector <long long>> Graf :: royFloyd(vector <vector <long long>> matrice)
{
    for (int t = 0; t < nrNoduri; t++)
      for (int i = 0; i < nrNoduri; i++)
        for (int j = 0; j < nrNoduri; j++)
            if (matrice[i][t] + matrice[t][j] < matrice[i][j])
                    matrice[i][j] = matrice[i][t] + matrice[t][j];
    return matrice;
}

///DiametrulUnuiArbore
int Graf :: diametruArbore()
{
    int maxim = 0, ultimulElement;
    vector <int> rez = BFS(1);
    for (int i = 1; i < rez.size(); i++)
        if (rez[i] > maxim)
        {
            maxim = rez[i];
            ultimulElement = i;
        }
    rez = BFS(ultimulElement);
    maxim = 0;
    for (int i = 1; i < rez.size(); i++)
        if (rez[i] > maxim)
            maxim = rez[i];
    return maxim + 1;
}

///FluxMaxim
bool Graf :: bfsFlux(vector <int> &tata, vector <vector <int>> &grafRezidual)
{
    vector <bool> vizitat(nrNoduri + 1, false);
    queue <int> coada;
    coada.push(1);
    vizitat[1] = true;
    tata[1] = -1;
    while(!coada.empty())
    {
        int nod_curent = coada.front();
        for (int i = 1; i <= nrNoduri; i++)
           if (vizitat[i] == false && grafRezidual[nod_curent][i] > 0)
           {
               if (i == nrNoduri)
               {
                   tata[i] = nod_curent;
                   return true;
               }
               coada.push(i);
               tata[i] = nod_curent;
               vizitat[i] = true;
            }
        coada.pop();
    }
    return false;
}

int Graf :: fluxMaxim()
{
    int fluxul_maxim = 0, flux_curent, tata_curent;
    vector <vector <int>> grafRezidual(nrNoduri + 1, vector <int>(nrNoduri + 1, 0));
    vector <int> tata(nrNoduri + 1, 0);
    for (int i = 1; i <= nrNoduri; i++)
         for (int j = 1; j <= nrNoduri; j++)
             grafRezidual[i][j] = listaAdiacenta[i][j];
    while (bfsFlux(tata, grafRezidual) == true)
    {
        flux_curent = INT_MAX;
        for (int v = nrNoduri; v != 1; v = tata[v])
        {
            tata_curent = tata[v];
            flux_curent = min(flux_curent, grafRezidual[tata_curent][v]);
        }
        for (int v = nrNoduri; v != 1; v = tata[v])
        {
            tata_curent = tata[v];
            grafRezidual[v][tata_curent] += flux_curent;
            grafRezidual[tata_curent][v] -= flux_curent;
        }
        fluxul_maxim += flux_curent;
    }
    return fluxul_maxim;
}

///---------------------Graf Ponderat - Muchii cu costuri-------------------------------
class GrafPonderat : public Graf
{
    private:
        vector <vector <pair<int, int>>> muchiiCuCost;

        ///Functii APM Kruskal
        int find_tata(int, vector <int>); ///gaseste tatal
        void set_tata(int, int, vector <int> &); ///seteaza tatal
    public:
        GrafPonderat(int, int, vector <vector <int>>, vector <vector<pair <int, int>>>);

        vector <pair<int, int>> apmKruskal(ostream &, vector <vector <int>>); ///returneaza muchiile din APM si afiseaza costul total si numarul muchiilor din APM

        vector <int> dijkstra(); ///returneaza vectorul de distante minime, plecand din nodul 1

        vector <int> bellmanford(ostream &); ///returneaza vectorul de distante minime, plecand din nodul 1. Daca nu se poate aplica, afiseaza mesajul "Ciclu negativ!"
};

GrafPonderat :: GrafPonderat(int nrNodurioduri, int nrMuchiiuchii, vector <vector <int>> lista, vector <vector<pair<int, int>>> muchiiCost) : Graf(nrNodurioduri, nrMuchiiuchii, lista) ///apelam constructorul din baza
{
    muchiiCuCost = muchiiCost;
}

///Apm - Kruskal - O(MlogN)
int GrafPonderat :: find_tata(int nod, vector <int> tata)
{
    while (nod != tata[nod])
        nod = tata[nod];
    return nod;
}

void GrafPonderat :: set_tata(int nod1, int nod2, vector <int> &tata)
{
    tata[nod1] = tata[nod2];
}

vector <pair<int, int>> GrafPonderat :: apmKruskal(ostream &out, vector <vector <int>> muchiiCost)
{
    vector <pair<int, int>> rez;
    vector <int> tata(nrNoduri + 1);
    for (int i = 1; i <= nrNoduri; i++)
        tata[i] = i;
    sort (muchiiCost.begin(), muchiiCost.end(), [] (vector <int> v1, vector <int> v2){return v1[2] < v2[2];}); ///sortam muchiile crescator dupa cost
    int cost_total = 0, nod1, nod2, tata1, tata2, nrMuchiiuchiiAPM = 0, index_muchie = 0;
    while (nrMuchiiuchiiAPM < nrNoduri - 1) ///parcurgem muchiile pana cand avem suficiente ca graful sa fie conex = (numar noduri - 1) muchii
    {
        nod1 = muchiiCost[index_muchie][0]; ///nod1 din muchia curenta
        nod2 = muchiiCost[index_muchie][1]; ///nod2 din muchia curenta
        ///cautam radacina arborilor partiali din care fac parte nodurile
        tata1 = find_tata(nod1, tata);
        tata2 = find_tata(nod2, tata);
        if (tata1 != tata2) ///am gasit muchie de adaugat in APM
        {
            if (tata1 < tata2)
                set_tata(tata1, tata2, tata);
            else
                set_tata(tata2, tata1, tata);
            rez.push_back(make_pair(nod1, nod2));
            cost_total = cost_total + muchiiCost[index_muchie][2];
            nrMuchiiuchiiAPM++;
        }
        index_muchie++;
    }
    out << cost_total << "\n";
    out << nrMuchiiuchiiAPM << "\n";
    return rez;
}

///Dijkstra - O(MlogN)
vector <int> GrafPonderat :: dijkstra()
{
    vector <int> distante(nrNoduri + 1, INT_MAX); ///initial distantele sunt egale cu infinit
    vector <int> inCoada(nrNoduri + 1, 0);
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair <int, int>>> coada; ///perechi {cost, nod}
    distante[1] = 0;
    coada.push({0, 1});
    inCoada[1] = 1;
    while (!coada.empty())
    {
        int nodCurent = coada.top().second;
        coada.pop();
        inCoada[nodCurent] = 0;
        for (int i = 0; i < muchiiCuCost[nodCurent].size(); i++)
        {
            int vecin, cost_vecin;
            vecin = muchiiCuCost[nodCurent][i].first;
            cost_vecin = muchiiCuCost[nodCurent][i].second;
            if (distante[nodCurent] + cost_vecin < distante[vecin])
    ///daca distanta pana la nodul curent + costul pana la nodul adiacent < distanta nodului adiacent, actualizam aceasta distanta
            {
                distante[vecin] = distante[nodCurent] + cost_vecin;
                if (inCoada[vecin] == 0)
                {
                    coada.push({distante[vecin], vecin});
                    inCoada[vecin] = 1;
                }
            }
        }
    }
    return distante;
}

///Bellmanford - O(MNlogN)
vector <int> GrafPonderat :: bellmanford(ostream &out) ///relaxam de nr_noduri-1 ori
{
    vector <int> distante(nrNoduri + 1, INT_MAX);
    vector <int> inCoada(nrNoduri + 1, 0);
    vector <int> vizitat(nrNoduri + 1, 0);
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair <int, int>>> coada;
    int ok = 1;
    distante[1] = 0;
    coada.push({0, 1});
    inCoada[1] = 1;
    while (!coada.empty())
    {
        int nodCurent = coada.top().second;
        coada.pop();
        inCoada[nodCurent] = 0;
        vizitat[nodCurent]++;
        if (vizitat[nodCurent] > nrNoduri - 1) ///daca am vizitat un nod de mai mult de (nr_noduri - 1) ori
        {
             ok = 0; ///am ciclu negativ
             break;
        }
        for (int i = 0; i < muchiiCuCost[nodCurent].size(); i++)
        {
            int vecin, cost_vecin;
            vecin = muchiiCuCost[nodCurent][i].first;
            cost_vecin = muchiiCuCost[nodCurent][i].second;
            if (distante[nodCurent] + cost_vecin < distante[vecin])
            {
                distante[vecin] = distante[nodCurent] + cost_vecin;
                if (inCoada[vecin] == 0)
                {
                    coada.push({distante[vecin], vecin});
                    inCoada[vecin] = 1;
                }
            }
        }
    }
    if (ok == 0)
        out << "Ciclu negativ!";
    else
        return distante;
}

///-------------------------BFS------------------------------
void problemaBFS()
{
    int n, s, st, dr, m;
    /*cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti nodul start: ";
    cin >> s;
    cout << "Introduceti muchiile: ";*/
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    fin >> n >> m >> s;
    vector <vector<int>> listaAdiacenta(n + 1);
    for (int i = 1; i <= m; i++)
    {
       // cin >> st >> dr;
        fin >> st >> dr;
        listaAdiacenta[st].push_back(dr);
    }
    Graf g(n, m, listaAdiacenta);
    vector <int> cost = g.BFS(s);
    for (int i = 1; i <= n; i++)
        fout << cost[i] << " ";
    fin.close();
    fout.close();
}

///-------------------------DFS--------------------------------
void problemaDFS()
{
    int n, m, st, dr;
    /*cout << "Numerotare noduri de la index 1! Graf neorientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";*/
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    fin >> n >> m;
    vector <vector<int>> listaAdiacenta(n + 1);
    for (int i = 1; i <= m; i++)
    {
       // cin >> st >> dr;
        fin >> st >> dr;
        listaAdiacenta[st].push_back(dr);
        listaAdiacenta[dr].push_back(st);
    }
    Graf g(n, m, listaAdiacenta);
    int rez = g.nr_componente_conexe();
    fout << rez;
    fin.close();
    fout.close();
}

///------------------Havel Hakimi-------------------------
void problemaHavelHakimi()
{
    vector <int> v;
    int n, el;
    cout << "Introduceti numarul de elemente: ";
    cin >> n;
    cout << "Introduceti gradele: ";
    for (int i = 0; i < n; i++)
    {
        cin >> el;
        v.push_back(el);
    }
    vector <vector <int>> vgol = {};
    Graf g(0, 0, vgol);
    bool rez = g.HavelHakimi(v, n);
    if (rez == true)
        cout << "Da, exista graf!";
    else cout << "Nu, nu exista graf!";
}

///------------------Sortare Topologica------------------
void problemaSortareTopologica()
{
    int n, m, st, dr;
    /*cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";*/
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    fin >> n >> m;
    vector <int> grade (n + 1, 0);
    vector <vector<int>> listaAdiacenta (n + 1);
    for (int i = 1; i <= m; i++)
    {
       // cin >> st >> dr;
        fin >> st >> dr;
        listaAdiacenta[st].push_back(dr);
        grade[dr]++;
    }
    Graf g(n, m, listaAdiacenta);
    vector <int> rez = g.sortareTopologica(grade);
    for (int i=0; i < rez.size(); i++)
        fout << rez[i] << " ";
    fin.close();
    fout.close();
}

///---------------Componente Tare Conexe-------------------
void problemaComponenteTareConexe()
{
    int n, m, st, dr;
   /* cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";*/
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> n >> m;
    vector <vector<int>> listaTr(n + 1);
    vector <vector<int>> listaAdiacenta(n + 1);
    for (int i = 1; i <= m; i++)
    {
        //cin >> st >> dr;
        fin >> st >> dr;
        listaAdiacenta[st].push_back(dr);
        listaTr[dr].push_back(st);
    }
    Graf g(n, m, listaAdiacenta);
    vector <vector <int>> rez = g.CTC(listaTr);
    int nrCTC = 0;
    for (int i = 0; i < rez.size(); i++)
       if (rez[i].size() != 0)
           nrCTC++;
    fout << nrCTC << "\n";
    for (int i = 0; i < rez.size(); i++)
    {
       if (rez[i].size() != 0)
        {
           for (int j = 0; j < rez[i].size(); j++)
              fout << rez[i][j] << " ";
           fout << "\n";
        }
    }
    fin.close();
    fout.close();
}

///------------------Muchii Critice---------------------
void problemaCriticalConnectionsLeetCode()
{
    int n, m, st, dr;
    cout << "Numerotare noduri de la index 0! Graf neorientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";
    vector <vector<int>> listaAdiacenta(n + 1);

    for (int i = 1; i <= m; i++)
    {
        cin >> st >> dr;
        listaAdiacenta[st].push_back(dr);
        listaAdiacenta[dr].push_back(st);
    }
    Graf g(n, m, listaAdiacenta);
    cout << "Muchii critice: ";
    vector <pair <int, int>> rez = g.muchiiCritice();
    for (int i = 0; i < rez.size(); i++)
        cout << rez[i].first << " " << rez[i].second << "\n";
}

///---------------Paduri De Multimi Disjuncte------------------
void problemaPaduriDeMultimiDisjuncte()
{
    ifstream fin("disjoint.in");
    ofstream fout("disjoint.out");
    int n, m, st, dr, operatie;
    fin >> n >> m;
    /*cout << "Introduceti numarul de multimi: ";
    cin >> n;
    cout << "Introduceti numarul de operatii efectuate: ";
    cin >> m;
    cout << "Operatie 1: Reuneste multimile unde se afla elementul x, respectiv y" << "\n";
    cout << "Operatie 2: Afiseaza 'DA' daca cele doua elemente se afla in aceeasi multime, 'NU' in caz contrar" << "\n";
    cout << "Introduceti valorile de forma: operatie - elementul x - elementul y: ";*/
    vector <vector<int>> vgol = {};
    vector <int> tata(n + 1);
    vector <int> rang(n + 1, 0);
    Graf g(n, m, vgol);
    for (int i = 1; i <= n; i++)
           tata[i] = i;
    for (int i = 1; i <= m; i++)
    {
        fin >> operatie >> st >> dr;
        if (operatie == 1)
        {
            g.Union(st, dr, tata, rang);
        }
        else if (g.Find(st, tata) == g.Find(dr, tata))
                 fout << "DA" << "\n";
             else fout << "NU" << "\n";
    }
    fin.close();
    fout.close();
}

///---------------------APM Kruskal-------------------------
void problemaAPMKruskal()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, st, dr, cost;
    //cout << "Introduceti numarul de noduri: ";
    //cin >> n;
    //cout << "Introduceti numarul de muchii: ";
    //cin >> m;
    //cout << "Introduceti muchiile si costul acestora: " << "\n";
    fin >> n >> m;
    vector <vector <int>> lista = {};
    vector <vector<pair <int, int>>> muchiiCuCost = {{}};
    vector <vector <int>> muchiiCost;
    for (int i = 1; i <= m; i++)
    {
       // cin >> st >> dr >> cost;
        fin >> st >> dr >> cost;
        muchiiCost.push_back({st, dr, cost});
    }
    GrafPonderat g(n, m, lista, muchiiCuCost);
    vector <pair<int, int>> rezultat = g.apmKruskal(fout, muchiiCost);
    for (int i = 0; i < rezultat.size(); i++)
       fout << rezultat[i].first << " " << rezultat[i].second << "\n";
    fin.close();
    fout.close();
}

///----------------------------Dijkstra----------------------------------
void problemaDijkstra()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m, st, dr, cost;
    fin >> n >> m;
    vector <vector <int>> lista = {};
    vector <vector<pair <int, int>>> muchiiCuCost(n + 1);
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr >> cost;
        muchiiCuCost[st].push_back(make_pair(dr, cost));
    }
    GrafPonderat g(n, m, lista, muchiiCuCost);
    vector <int> rez = g.dijkstra();
    for (int i = 2; i < rez.size(); i++)
        if (rez[i] == INT_MAX)
            fout << 0 << " ";
        else
            fout << rez[i] << " ";
    fin.close();
    fout.close();
}

///-------------------------Bellmanford---------------------------------
void problemaBellmanford()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int n, m, st, dr, cost;
    fin >> n >> m;
    vector <vector <int>> lista = {};
    vector <vector<pair <int, int>>> muchiiCuCost(n + 1);
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr >> cost;
        muchiiCuCost[st].push_back(make_pair(dr, cost));
    }
    GrafPonderat g(n, m, lista, muchiiCuCost);
    vector <int> rez = g.bellmanford(fout);
    for (int i = 2; i < rez.size(); i++)
            fout << rez[i] << " ";
    fin.close();
    fout.close();
}

///------------------------Roy Floyd--------------------------------------
void problemaRoyFloyd()
{
    ifstream fin("royfloyd.in");
    ofstream fout("royfloyd.out");
    int n,el;
    fin >> n;
    vector <vector <long long>> matrice(n + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
           fin >> el;
           if (el == 0 && i != j)
               matrice[i].push_back(INT_MAX);
           else
               matrice[i].push_back(el);
        }
    vector <vector <int>> lista = {};
    Graf g(n, 0, lista);
    vector <vector <long long >> rez = g.royFloyd(matrice);
    for (int i = 0; i < n; i++)
    {
         for (int j = 0; j < n; j++)
            if (rez[i][j] != INT_MAX)
                fout << rez[i][j] << " ";
            else
                fout << 0 << " ";
         fout << "\n";
    }
    fin.close();
    fout.close();
}

///-----------------------Diametrul Unui Arbore-----------------------------
void problemaDiametrulUnuiArbore()
{
    int n, m, st, dr;
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> n;
    vector <vector <int>> listaAdiacenta(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        fin >> st >> dr;
        listaAdiacenta[st].push_back(dr);
        listaAdiacenta[dr].push_back(st);
    }
    Graf g(n, n - 1, listaAdiacenta);
    int rez = g.diametruArbore();
    fout << rez;
    fin.close();
    fout.close();
}

///----------------------Flux maxim--------------------------
void problemaFluxMaxim()
{
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    int n, m, st, dr, cost;
    fin >> n >> m;
    vector <vector <int>> listaAdiacenta(n + 1, vector <int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr >> cost;
        listaAdiacenta[st][dr] = cost;
    }
    Graf g(n, m, listaAdiacenta);
    int flux_maxim = g.fluxMaxim();
    fout << flux_maxim;
    fin.close();
    fout.close();
}

int main()
{
    problemaDiametrulUnuiArbore();
}