#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <set>
#include<cstdio>

using namespace std;

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

//strucutra unui arc cu distanta(cost) din graf (folosita in metodele Dijkstra si Bellman_Ford si de clasa Min_heap)
struct arc
{
    int y, distanta;
    arc(int b, int d)
    {
        y = b;
        distanta = d;
    }
    arc(){}
    bool operator < (const arc &a) const //operator pentru compararea distantelor(costurilor) a doua arce
    {return distanta < a.distanta;}
};


class Graf
{

private:

    //strucutra unei muchii din graf(folosita in medota Biconexe)
    struct muchie
    {
        int x,y;
        muchie(int a, int b)
        {
            x=a;
            y=b;
        }
        muchie(){}
    };

    //strucutra unei muchii cu cost din graf(folosita in medota Kruskal)
    struct muchie_cost
    {
        int x,y,cost;
        muchie_cost(int a, int b, int c)
        {
            x=a;
            y=b;
            cost=c;
        }
        muchie_cost(){}
        bool operator < (const muchie_cost &m) const //operator pentru compararea costurilor a doua muchii
        {return cost < m.cost;}
    };


    int n; //nr de noduri

    int m; //nr de muchii

    //vectorul in care se va construi rezultatul functiilor recursive
    vector<int> rezultat;

    //vectorul de tati folosit in parcurgeri(vector utilizat in comun de metodele BfsMaxFlow si MaxFlow)
    vector<int> tati;

    //vector folosita in parcurgeri pentru a retine ce noduri au fot vizitate
    vector<bool> vizitat;

    //matrice in care se moreaza fluxurile dintre doua noduri adiacente din graf(utilizat in comun de metodele BfsMaxFlow si MaxFlow)
    vector<vector<int>> flux;

    //matrice in care se moreaza capacitatile dintre doua noduri adiacente din graf(utilizat in comun de metodele BfsMaxFlow si MaxFlow)
    vector<vector<int>> capacitate;

    //vector cu listele de adiacenta
    vector<vector<int>> la;

    //vector de muchii cu cost
    vector<muchie_cost> vmc;

    //vector cu listele de adiacenta ale nodurilor dintr-un graf orientat(folosita pentru metodele Dijkstra si Bellman_Ford)
    vector<vector<arc>> arce;

    //variabila care semnaleaza daca graful este orientat sau nu(daca este orientat este true altfel este false)
    bool orientat;

    //variabila care semnaleaza daca muchiile grafului au sau nu asociate costuri(daca da costuri este true altfel este false)
    bool costuri;

   //subprogram recursiv ce executa parcurgerea in adancime a grafului(folosit de metodele Dfs si DfsNrConexe)
    void DfsRec(int x);

    //subprogram de tip Dfs folosit de metoda MuchiiCritice
    void DfsMc(int x, int parinte, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result, vector<bool> & vizitat);

    //subprogram de tip Dfs folosit de metoda Biconexe
    void DfsBcx(int x, int parinte, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe, vector<bool> & vizitat);

    //subprogram de tip Dfs folosit de metoda ComponenteTareConexe
    void DfsCtc(int x, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe, vector<bool> & vizitat);

    //metoda ce implementeaza o parcurgere Bfs si intoarce false daca din sursa nu se poate ajunge in destinatie, folosita in algoritmul Edmonds-Karp
    bool BfsMaxFlow(int S, int D);

    //subprogram folosit de metoda HamiltonCostMinim pentru a calcula costul lantului de la nodul 0
    //la nodul destinatie, drum ce trece doar prin noduri ce au bitul corespunzator din scrierea binara a mastii cu valoarea 1
    int Calc(int nod_dest, int masca,  vector<vector<int>> &M);

    //metoda ce implementeaza o parcurgere Dfs care cauta si returneaza true daca gaseste un cuplaj
    //pentru nodul dat(nod va fi mereu din multimea L) si in acelasi timp seteaza cuplajul
    bool DfsCuplaj(int nod, vector<int>&L, vector<int>&R);


public:

    //constructor parametrizat care primeste si tipul grafului si daca muchiile au sau nu costuri: orientat(tip==true)
    //sau neorientat(tip==false) si cu costuri pe muchii(costuri==true) sau fara(costuri==false)
    Graf(int n, int m, bool orientat, bool costuri);

    //metoda de adaugare a unei muchii in graf(daca graful este neorientat va adauga atat muchia x-y cat si muchia y-x)
    void AddEdge(int x, int y);

    //metoda de adaugare a unei muchii cu cost in graf
    void AddEdgeCost(int x, int y, int c);

    //metoda de adaugare a unui arc cu distanta in graf
    void AddArc(int x, int y, int d);


    vector<int> Dfs(int x);

    //metoda ce retureaza numarul de componente conexe ale grafului dat, prin parcurgere in adancime ce pleaca din nodul x
    int DfsNrConexe(int x);


    vector<int> Bfs(int x);

    //metoda ce returneaza vectorul de distante de la nodul x la toate celelalte noduri
    vector<int> BfsDistante(int x);


    vector<int> SortareTop();

    //metoda ce afiseaza vectorul de componente biconexe(vectori de noduri) ale grafului
    vector<set<int>> Biconexe();

    //metoda ce afiseaza vectorul de muchii critice(vectori cu 2 elemente) ale grafului
    vector<vector<int>> MuchiiCritice();

    //metoda ce afiseaza vectorul de componente  tareconexe(seturi de noduri)
    vector<set<int>> ComponenteTareConexe();

    //metoda ce implementeaza algoritmul lui Kruskal de determinare a APM-ului
    vector<pair<int,int>> Kruskal(int &cost_total);

    //metoda ce implementeaza algoritmul lui Dijkstra de determinare a drumurilor minime de la un nod dat
    //la toate celelalte, folosind un heap
    vector<int> Dijkstra(int s);

    //metoda ce implementeaza algoritmul Bellman-Ford de determinare a drumurilor minime de la un nod dat la toate celelalte,
    //depistand ciclurile de cost negativ. Algoritmul floseste o coada
    vector<int> BellmanFord(int s);

    //metoda ce implementeaza algoritmul Edmonds-Karp de determinarea a fluxului maxim ce poate fi trimis printr-o
    //retea(graf orientat alea carui muchii au asociate capacitati)
    int MaxFlow(int S, int D);

    //metoda ce implementeaza algoritmul Roy-Floyd de determinare a matricei de drumuri minime dintr-un graf
    vector<vector<int>> RoyFloyd();

    //metoda ce returneaza diametrul arborelui(disanta dintre cele mai indepartate doua frunze ale arborelui)
    int Darb();

    //metoda ce returneaza un ciclu eulerian din graf, daca acesta exista sau -1 in caz contrar
    vector<int> CicluEuler();

    //metoda ce returneaza costul minim al unui ciclu hamiltonian daca graful dat are un astfel de ciclu
    int HamiltonCostMinim();

    //metoda ce returneaza un cuplaj maxim al unui graf bipartit
    vector<pair<int,int>> CuplajMaxim(int n1, int n2);
};




//clasa de multimi disjuncte folosita la algoritmul lui Kruskal
class DisjointSets
{
private:

    //numarul de noduri
    int n;

    //vectorul de reprezentanti(conform cursului)
    vector<int> rep;

    //vector ce va retine inaltimile arborilor
    vector<int> h;

public:

    //constructor parametrizat care face si initializarea vectorului de preprezentanti
    DisjointSets(int n);

    //metoda ce returneaza reprezentantul unui nod x dat
    int Reprezentant(int x);

    //metoda ce reuneste arborii care contin nodurile x si y
    void Reuniune(int x, int y);
};

DisjointSets::DisjointSets(int n)
{
    this->n = n;

    //initializam vectorul de reprezentanti si pe cel de inaltimi
    rep.resize(n+1);
    h.resize(n+1);

    for(int i=1; i<=n; ++i)
        rep[i] = i;
};

int DisjointSets::Reprezentant(int x)
{
    //daca x este chiar radacina(adica daca el este reprezentantul sau) il returnez
    if(x == rep[x])
        return x;
    else //altfel reprezentantul lui x va fi reprezentantul tatalui sau(apel recursiv)
    {
        //efectuam compresia asupra arborelui
        int r = Reprezentant(rep[x]); //aflu reprezentantul parintelui lui x
        rep[x] = r;

        //returnam reprezentantul lui x
        return r;
    }
}

void DisjointSets::Reuniune(int x, int y)
{
    //aflam rep lui x si y
    int rx = Reprezentant(x);
    int ry = Reprezentant(y);

    //daca x si y au acelasi reprezentant, atunci acestia sunt deja in aceeasi multime(nu am ce sa reunesc)
    if(rx == ry)
        return;

    //subordonez reprezentantul din arborele cu inaltime mai mica reprezentantului din arborele cu inaltime mai mare
    if(h[rx] < h[ry])
        rep[rx] = ry;
    else if(h[rx] > h[ry])
        rep[ry] = rx;
    else //altfel inseamna ca au inaltimi egale, caz in care inaltimea creste cu 1 dupa subordonare
    {
        rep[rx] = ry;
        h[ry]++;
    }
}



//clasa Min_heap folosita la pastrarea in ordinea crescatoare a distantelor(costurilor) arcelor din graf (folosita in metoda Dijsktra)
class Min_heap
{
private:

    //nr de noduri din heap
    int n;

    //numarul de noduri distincte din heap
    int N;

    //vector de arce prin care este reprezentat heap-ul
    vector<arc> h;

    //vector ce retine pe ce pozitie in heap se afla fiecare nod x
    vector<int> pozitii;


public:

    //constructor parametrizat pt heap
    Min_heap(int n);

    //metoda care scoate minimul din heap(varful)
    arc pop();

    //metoda care insereaza in heap un arc
    void push(arc a);

    //metoda de deplasare in jos in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
    void go_down(int i, int n);

    //metoda de deplasare in sus in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
    void go_up(int i);

    //metoda care obtine pozitia fiului minim al unui nod abia inserta in heap
    int poz_min(int i, int n);

    //metoda care testeaza daca heap-ul este gol
    bool empty();

};

bool Min_heap::empty()
{
    if(N==0)
        return true;
    else
        return false;
}

Min_heap::Min_heap(int n)
{
    h.resize(n+1);
    pozitii.resize(n+1);
    N = 0;
}

int Min_heap::poz_min(int i, int n)
{
    //daca nodul este frunza
    if(2*i>n)
        return 0;

    //daca nodul nu este frunza si exista ambii descendent
    if(2*i + 1 <= n)
    {
        if(h[2*i].distanta <= h[2*i+1].distanta)
            return 2*i;
        else
            return 2*i+1;
    }
    else //altfel inseamna ca nodul nu este frunza dar am doar descendent stang
        return 2*i;
}

void Min_heap::go_up(int i)
{
    //daca nodul nu este deja in varf
    if(i>1)
    {
        //aflu parintele
        int p = i/2;

        if(h[i] < h[p])
        {
            pozitii[h[i].y] = p;
            pozitii[h[p].y] = i;
            arc aux = h[p];
            h[p] = h[i];
            h[i] = aux;
            go_up(p);
        }
    }
}

void Min_heap::go_down(int i, int n)
{
    //daca nodul nu este deja frunz
    if(i<=n/2)
    {
        //aflu pozitia celui mai mic dintre fii
        int m = poz_min(i,n);

        if(h[m] < h[i])
        {
            pozitii[h[i].y] = m;
            pozitii[h[m].y] = i;
            arc aux = h[m];
            h[m] = h[i];
            h[i] = aux;
            go_down(m, n);
        }
    }
}

arc Min_heap::pop()
{
    pozitii[h[N].y] = 1;
    pozitii[h[1].y] = 0;
    arc aux = h[1];
    h[1] = h[N];
    h[N] = aux;
    N--;
    go_down(1, N);
    return h[N+1];
}

void Min_heap::push(arc a)
{
    //daca nodul y deja exista in heap il elimin, pentru a ne asigura ca un nod nu apare de mai multe ori in heap
    if(pozitii[a.y]>0)
    {
        arc aux = h[pozitii[a.y]];
        pozitii[h[N].y] = pozitii[a.y];
        h[pozitii[a.y]] = h[N];
        h[N] = aux;
        N--;
        go_down(pozitii[a.y], N);
    }

    //adaug noul nod in heap si memorez pozitia sa
    N++;
    h[N] = a;
    pozitii[a.y] = N;
    go_up(N);
}




Graf::Graf(int n, int m, bool orientat, bool costuri)
{
    this->n = n;
    this->m = m;
    this->orientat = orientat;
    this->costuri = costuri;
    la.resize(n+1);
    arce.resize(n+1);

}


void Graf::AddEdge(int x, int y)
{
    la[x].push_back(y);
    if(!orientat)
        la[y].push_back(x);
}


void Graf::AddEdgeCost(int x, int y, int c)
{
    vmc.push_back(muchie_cost(x,y,c));
}


void Graf::AddArc(int x, int y, int d)
{
    arce[x].push_back(arc(y,d));
}


void Graf::DfsRec(int x)
{

    vizitat[x] = true;
    rezultat.push_back(x);
    for(int i=0; i<la[x].size(); ++i)
    {
        int y = la[x][i];

        if (vizitat[y] == false)
        {
            DfsRec(y);
        }
    }
}


int  Graf::DfsNrConexe(int x)
{
    if(orientat == true)
    { cout << "Metoda DfsNrConexe este folosita doar la grafurile neorientate!\n";
        return -1;
    }

    vizitat.clear();
    vizitat.resize(n+1, 0);

    int conexe=0;

    for(int i=1; i<=n; ++i)
        if(vizitat[i]!=1)
        {
            conexe++;
            DfsRec(i);
        }

    return conexe;
}


vector<int> Graf::Dfs(int x)
{

    tati.clear();
    tati.resize(n+1);
    rezultat.clear();
    vizitat.clear();
    vizitat.resize(n+1, 0);
    DfsRec(x);

    return rezultat;
}


vector<int> Graf::BfsDistante(int x)
{
    if(orientat == false)
    { cout << "Metoda BfsDistante este folosita doar la grafurile orientate!\n";
        return {};
    }


    vizitat.clear();
    rezultat.clear();
    rezultat.resize(n+1, -1);
    vizitat.resize(n+1);

    queue<int> q;

    q.push(x);
    vizitat[x]=1;
    rezultat[x]=0;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        for(int i=0; i<la[x].size(); ++i)
        {
            int y=la[x][i];
            if(!vizitat[y])
            {
                q.push(y);
                vizitat[y]=true;
                rezultat[y]=rezultat[x]+1;
            }
        }
    }
    return rezultat;
}


vector<int> Graf::Bfs(int x)
{
    vizitat.clear();
    tati.clear();
    rezultat.clear();
    vizitat.resize(n+1);
    tati.resize(n+1);
    queue<int> q;
    q.push(x);
    vizitat[x]=1;

    while(!q.empty())
    {
        x = q.front();
        rezultat.push_back(x);
        q.pop();
        for(int i=0; i<la[x].size(); ++i)
        {
            int y=la[x][i];
            if(!vizitat[y])
            {
                q.push(y);
                tati[y]=x;
                vizitat[y]=true;
            }
        }
    }
    return rezultat;
}


vector<int> Graf::SortareTop()
{
    if(orientat == false)
    { cout << "Metoda SortareTop este folosita doar la grafurile orientate aciclice!\n";
        return {};
    }


    //completam vector in care retinem gradele interioare ale nodurilor
    vector<int> gr_int(n+1);
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<la[i].size(); ++j)
            ++gr_int[la[i][j]];
    }

    queue<int> q; //coada folosita la sortarea topologica
    //parcurgem vectorul de grade si punem in coada nodurile cu gradul interior 0
    for(int i=1; i<=n; ++i)
        if(gr_int[i]==0)
            q.push(i);

    //parcurgem coada pentru a obtine o sortare topologica
    vector<int> rez;
    rez.reserve(n+1);
    while(!q.empty())
    {
        int x;
        //extragem un nod din coada
        x = q.front();
        q.pop();
        //scadeam gradele interioare ale nodurilor in care intra nodul curent
        for(int i=0; i<la[x].size(); ++i)
        {
            int y = la[x][i];
            --gr_int[y];
            if(gr_int[y] == 0)
                q.push(y);
        }
        rez.push_back(x);
    }
    return rez;

}


void Graf::DfsBcx(int x, int parinte, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe, vector<bool> & vizitat)
{

    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            stiva.push(muchie(x,z));//adaug muchia in stiva de muchii
            DfsBcx(z, x, moment, low, stiva, timp, biconexe, vizitat);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];


            //determinare componente biconexe
            if(moment[x] <= low[z]) //deci x este punct critic
            {
                set<int> componenta;
                int a, b; //capetele unei muchii
                do
                {
                    muchie m=stiva.top();
                    stiva.pop();
                    a=m.x;
                    b=m.y;
                    componenta.insert(a);
                    componenta.insert(b);
                }while(a!=x || b!=z);
                biconexe.push_back(componenta);//adaug componenta in vectorul de componente biconexe
            }

        }
        else //am dat de o muchie de intoarcere
        {
            if(z!=parinte) //verific ca z sa nu fie parinte al lui x
            {    //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
                // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
                // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
                if (low[x] > moment[z])
                    low[x] = moment[z];
            }
        }
    }
}


vector<set<int>> Graf::Biconexe()
{

    vector<set<int>> biconexe; //vectorul de componente biconexe
    if(orientat == true)
    { cout << "Metoda Biconexe este folosita doar la grafurile neorientate!\n";
        return biconexe;
    }

    vector<bool> vizitat(n+1); //vector vizitat
    vector<int> moment(n+1); //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    stack<muchie> stiva; //stiva in care vom retine muchiile unei componente biconeexe


    int timp = 0;// timp = contor de timp pentru crearea vectorului moment

    //daca graful nu este conex, se analizeaza fiecare componenta conexa
    for(int i=1; i<=n; ++i)
        if(!vizitat[i])
            DfsBcx(i,0,moment,low,stiva, timp, biconexe, vizitat);


    return biconexe;
}


void Graf::DfsMc(int x, int parinte, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result, vector<bool> & vizitat)
{
    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            DfsMc(z, x, moment, low, timp, result, vizitat);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];


            //daca este muchie critica o adaugam in result
            if(low[z] > moment[x])
                result.push_back({x,z});

        }
        else //muchie de intoarcere
        {
            if(z!=parinte && low[x] > moment[z])
            {
                low[x] = moment[z];
            }
        }
    }
}


vector<vector<int>> Graf::MuchiiCritice()
{
    //vectorul de muchii critice
    vector<vector<int>> result;

    if(orientat == true)
    { cout << "Metoda MuchiiCritice este folosita doar la grafurile neorientate!\n";
        return result;
    }

    //vector vizitat
    vector<bool> vizitat(n+1);

    //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> moment(n+1);

    //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    vector<int> low(n+1);

    // timp = contor de timp pentru crearea vectorului moment
    int timp = 0;

    //daca graful nu este conex, se analizeaza fiecare componenta conexa
    for(int i=1; i<=n; ++i)
        if(!vizitat[i])
            DfsMc(i,0,moment,low, timp, result, vizitat);


    return result;
}


void Graf::DfsCtc(int x, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe, vector<bool> & vizitat)
{
    vizitat[x] = true;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    stiva.push(x);//adaug nodul in stiva de noduri si in multimea care tine evidenta nodurilor din stiva
    in_stack.insert(x);

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == false)
        {
            DfsCtc(z, moment, low, stiva, in_stack, timp, tareconexe, vizitat);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];

        }
        else if(in_stack.find(z)!=in_stack.end())//am dat de o muchie de intoarcere si nodul z face parte din noua componenta tare_conexa
        {
            //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
            // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
            // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
            if (low[x] > moment[z])
                low[x] = moment[z];
        }
    }
    if(low[x]==moment[x]) //daca nodul e radacina in componenta tare_conexa curenta(am avut un circuit)
    {
        set<int> componenta;
        int y;
        do{
            y=stiva.top();
            stiva.pop();
            in_stack.erase(y);
            componenta.insert(y);
        }while(y!=x);
        tareconexe.push_back(componenta);
    }
}


vector<set<int>> Graf::ComponenteTareConexe()
{
    //vectorul de componente tare-conexe
    vector<set<int>> tareconexe;

    if(orientat == false)
    { cout << "Metoda ComponenteTareConexe este folosita doar la grafurile orientate!\n";
        return tareconexe;
    }

    vector<bool> vizitat(n+1);

    //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> moment(n+1);

    //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    vector<int> low(n+1);

    //stiva in care vom retine nodurile unei componente tare-conexe
    stack<int> stiva;

    //multimne care retine ce elemente sunt in stiva la un anumit moment
    set<int> in_stack;

    int timp=0;

    //daca graful nu este conex, se analizeaza fiecare componenta tare-conexa
    for(int j=1; j<=n; ++j)
        if(vizitat[j]==0)
            DfsCtc(j, moment, low, stiva, in_stack, timp, tareconexe, vizitat);

    return tareconexe;
}


vector<pair<int,int>> Graf::Kruskal(int &cost_total)
{
    //complexitatea algoritmului este O(m*logn)
    if(orientat == true || costuri == false)
    { cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile neorientate conexe, ale caror muchii au asociate costuri!\n";
        return {};
    }

    //sortam vectorul de muchii crescator dupa cost(in M*logM)
    sort(vmc.begin(), vmc.end());

    //definim o padure de multimi disjuncte
    DisjointSets dj(n);

    //vectorul in care vom retine muchiile APM-ului
    vector<muchie> rezultat;

    //APM-ul va avea exact n-1 muchii(pt ca este arbore)
    rezultat.resize(n-1);

    //variabila care retine cate muchii au fost selectate pana la un anumit moment de timp
    int contor = 0;
    cost_total = 0;

    for(int i=0; i<m; ++i)
    {
        //obtin extremitatiile muchiei curente
        int x = vmc[i].x;
        int y = vmc[i].y;

        //aflu reprezentatntii lui x si y(pt a vedea daca sunt sau nu in multimi disjuncte)
        int rx = dj.Reprezentant(x);
        int ry = dj.Reprezentant(y);

        //au acelasi reprezentant muchia nu este buna si trec mai departe
        if(rx == ry)
            continue;

        //adaug muchia curenta in rezultat(in APM)
        rezultat[contor] = muchie(x,y);
        contor++;
        cost_total+=vmc[i].cost;

        //daca am atins numarul de muchii necesare APM-ului ne oprim
        if(contor == n-1)
            break;

        //reunim multimiile lui x si y
        dj.Reuniune(x,y);
    }
    vector<pair<int,int>> rez(contor+1);

    for(int i=0; i<contor; ++i)
    {
        rez[i].first = rezultat[i].x;
        rez[i].second = rezultat[i].y;

    }
    return rez;

}


vector<int> Graf::Dijkstra(int s)
{
    //complexitatea algoritmului este O(m*logn)
    if(costuri == false)
    { cout << "Metoda Dijkstra de determinare a drumurilor de cost minim este folosita doar la grafurile ale caror muchii au asociate costuri(distante)!\n";
        return {};
    }

    //initializare

    //vector de distante
    vector<int> d(n+1, 1000000001);

    //vectorul de tati
    vector<int> t(n+1, 0);
    d[s] = 0;

    //declaram heapul
    Min_heap H(n);

    //punem in heap distantele de la nodul de start la toate nodurile sale adiacente si actualizam tatal acestor noduri(care este chiar nodul de start)
    //impreuna cu distantele(care sunt chiar costurile muchiilor dintre nodul 1 si noduriel respective)
    for(int i=0; i<arce[s].size(); ++i)
    {
        H.push(arce[s][i]);
        d[arce[s][i].y] = arce[s][i].distanta;
        t[arce[s][i].y] = s;
    }

    //in mod repetat, pentru restul de n-1 noduri, selectez nodurile adiacente(la fiecare pas este ales nodul cu distanta cea mai mica
    //care nu a mai fost selectat)
    //cele in care se poate ajunge din ele
    while(!H.empty())
    {
        //arcul curent
        arc ac = H.pop();

        for(int i=0; i<arce[ac.y].size(); ++i)
        {
            //nodul in care s-a ajuns din  nodul curent
            int z = arce[ac.y][i].y;

            //noua distanta
            int nd = d[ac.y] + arce[ac.y][i].distanta;

            //relaxare muchie
            if(nd < d[z])
            {
                d[z] = nd;
                t[z] = ac.y;
                H.push(arc(z,nd));
            }
        }
    }

    for(int i=2; i<=n; ++i)
        if(d[i] == 1000000001)
            d[i]=0;
    return d;
}


vector<int> Graf::BellmanFord(int s)
{
    //complexitatea algoritmului este O(m*n)
    if(costuri == false)
    { cout << "Metoda BellmanFord de determinare a drumurilor de cost minim este folosita doar la grafurile ale caror muchii au asociate costuri(distante)!\n";
        return {};
    }

    //initializare

    //vector de distante
    vector<int> d(n+1, 1000000001);

    //vector ce retine de cate ori un nod a fost introdus in coada(de cate ori s-a modificat pe parcursul tuturor pasilor acel nod)
    vector<int> cnt(n+1, 0);

    //vector ce retine daca un nod a fost pus in coada sau nu(la un pas ne intereseaza doar daca unui nod
    // i se modifica distanta, nu de cate ori i se modifica distanta, asa ca nu il vom pune in coada de fiecare data cand i se modifica
    // distanta, ci doar o data)
    vector<int> selectat(n+1, 0);

    //vectorul de tati
    vector<int> t(n+1, 0);

    d[s] = 0;
    selectat[s] = 1;
    cnt[s] = 1;

    //coada in care se vor pune nodurile ale caror disante s-au modificat(pentru optimizarea algoritmului)
    queue<int> q;
    q.push(s);

    //fiecare iteratie a while-ului reprezinta un pas nou din algoritmul Bellman-Ford(poate avea cel mult n-1 pasi)

    bool circuit_negativ = false;

    while(!q.empty() && !circuit_negativ)
    {
        int u = q.front();
        selectat[u] = 0;

        //daca pt nodul u a fost modificata distanta de n ori oprim executia
        if(cnt[u] == n)
        {
            circuit_negativ = true;
            break;
        }
        q.pop();

        for (int j = 0; j < arce[u].size(); ++j)
        {
            int v = arce[u][j].y;

            // noua distanta folosita la eventuala relaxare
            int nd = d[u] + arce[u][j].distanta;

            //testare pentru relaxarea drumului
            if (nd < d[v])
            {
                d[v] = nd;
                t[v] = u;

                if(selectat[v] == 0)
                {
                    cnt[v] ++;
                    selectat[v] = 1;
                    q.push(v);
                }

            }
        }
    }

    if(circuit_negativ)
        return {};
    else
    {
        for(int i=2; i<=n; ++i)
            if(d[i] == 1000000001)
                d[i] = 0;
    }
    return d;
}


vector<vector<int>> Graf::RoyFloyd()
{
    //complexitatea algoritmului este O(n^3)

    //matricea drumurilor unui graf, folosita in algoritmul Roy-Floyd
    vector<vector<int>> md;

    if(costuri == false)
    {
        cout << "Metoda RoyFloyd este folosita doar la grafurile ale caror muchii au asociate costuri!\n";
        return md;
    }

    int inf = (1<<20);

    md.resize(n+1,vector<int>(n+1,inf));

    //construim matricea drumurilor din listele de adiacenta arce
    for(int i=1; i<=n; ++i)
        for(int j=0; j<arce[i].size(); ++j)
            if(arce[i][j].distanta!=0)
                md[i][j+1] = arce[i][j].distanta;

    //roy-floyd
    for(int k=1; k<=n; ++k)
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                if(md[i][k] + md[k][j] < md[i][j])
                    md[i][j] = md[i][k] + md[k][j];

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            if(md[i][j] == inf || i==j)
                md[i][j] = 0;

    return md;
}


bool Graf::BfsMaxFlow(int S, int D)
{
    //complexitatea algoritmului este O(n)
    tati[D] = 0;
    //golesc vectorul vizitat la fiecare parcurgere
    vizitat.clear();
    //redimensionam vectorul vizitat si il initializam
    vizitat.resize(n+1, 0);

    //coada folosita in parcurgerea Bfs
    queue<int> q;

    //punem in coada nodul de start
    q.push(S);
    tati[S] = 0;
    vizitat[S] = true;
    //cat timp coada nu este goala(mai am elemente de procesat) si nu s-a ajunj inca in destinatie
    //parcurg Bfs
    while(!q.empty() && tati[D] == 0)
    {
        //luam urmatorul element din coada
        int x = q.front();
        q.pop();

        //ii parcurgem lista de adiacenta
        for(int i=0; i<la[x].size(); ++i)
        {
            int y = la[x][i];

            //daca nodul adiacent curent nu a fost vizitat si arcul de la x la y este unul nesaturat
            if(vizitat[y] == true || capacitate[x][y] == flux[x][y])
                continue;

            tati[y] = x;
            vizitat[y] = true;
            q.push(y);
        }
    }

    if(tati[D]!=0)
        return true;
    else
        return false;

}


int Graf::MaxFlow(int S, int D)
{
    //complexitatea algoritmului este O(n*(m^2))

    if(costuri == false || orientat == false)
    {
        cout << "Metoda MaxFlow este folosita doar la grafurile orientate ale caror muchii au asociate costuri!\n";
        return -1;
    }

    //golesc vectorul tati
    tati.clear();
    //redimensionam vectorul tati si il initializam
    tati.resize(n+1, 0);

    int rez = 0;

    //dimensionam si initializam matricele flux si capacitate
    flux.resize(n+1, vector<int>(n+1, 0));
    capacitate.resize(n+1, vector<int>(n+1, 0));


    //completam matricea de capacitati(capacitatile sunt luate din listel de adiacenta)
    for(int i=1; i<=n; ++i)
        for(int j=0; j<arce[i].size(); ++j)
        {
            int y = arce[i][j].y;
            capacitate[i][y] += arce[i][j].distanta;
            la[i].push_back(y);
            la[y].push_back(i);
        }


    //cat timp gasesc un drum de ameliorare de la sursa la destinatie
    while(BfsMaxFlow(S, D))
    {

        for(int i=0; i<la[D].size(); ++i)
        {
            int y = la[D][i];
            if (flux[y][D] == capacitate[y][D] || !vizitat[y])
                continue;

            tati[D] = y;
            int a = (1<<30);
            //parcurg drumul de la D la S pentru a determina cu cat se poate modifica fluxul pe acel drum
            for (int i = D; i != S; i = tati[i])
                a = min(a, capacitate[tati[i]][i] - flux[tati[i]][i]);

            if (a == 0)
                continue;
            //parcurg din nou drumul pentru a face actualizarea
            for (int i = D; i != S; i = tati[i])
            {
                flux[tati[i]][i] += a;
                flux[i][tati[i]] -= a;
            }
            rez += a;
        }
    }

    return rez;
}


int Graf::Darb()
{
    //complexitatea algoritmului este O(n)

    //metoda utilizata doar la arbori(graf neorientat conex si aciclic)
    if(orientat == true)
    {
        cout << "Metoda Darb este folosita doar la arbori(graf neorientat conex si aciclic)!\n";
        return -1;
    }

    vector<int> parcurgere = Bfs(1);

    parcurgere = Bfs(parcurgere[n-1]);

    int diametru=0;

    int i = parcurgere[n-1];
    do
    {
        diametru+=1;
        i = tati[i];
    }while(i!=0);

    return diametru;
}


vector<int> Graf::CicluEuler()
{
    //complexitatea algoritmului este O(m)

    //verificam daca toate nodurile au grade pare(daca nu returnam -1)
    for(int i=1; i<=n; ++i)
    {
        if(arce[i].size()%2 != 0)
            return {-1};

    }

    vector<int> rezultat;
    vector<bool> mv;

    //vector ce retine pt fiecare muchie daca a fost sau nu vizitata
    mv.resize(m+1, 0);

    //declaram stiva si punem in ea primul nod vizitat
    stack<int> s;
    s.push(1);

    //cat timp stiva nu e goala(mai avem elemente de procesat)
    while(!s.empty())
    {
        //extragem nod din stiva
        int nod = s.top();
        //daca acesta mai are vecini
        if(!arce[nod].empty())
        {
            //extragem un vecin
            int y = arce[nod].back().y;
            int poz = arce[nod].back().distanta;
            arce[nod].pop_back();

            //stergem muchia dintre nodul curent si vecinul sau(din ambele liste de adiacenta)
            if(!mv[poz])
            {
                mv[poz] = true;
                s.push(y);
            }

        }
        else
        {
            s.pop();
            rezultat.push_back(nod);

        }

    }

    //scoatem ultimul nod deoarece apare si la inceputul lantului
    rezultat.pop_back();
    return rezultat;
}


int Graf::Calc(int nod_dest, int masca,  vector<vector<int>> &M)
{

    //daca in matricea de memoizare avem -1,
    //inseamna ca pana la acel punct nu s-a calculat valoarea
    //si o vom calcula pe baza valorilor din urma
    if(M[masca][nod_dest] == -1)
    {
        M[masca][nod_dest] = 100000000; //initializam cu infinit

        for(int i=0; i<la[nod_dest].size(); ++i)
            if((masca & (1<<la[nod_dest][i]))!=0) //daca pe pozitia aferenta nodului adiacent curent se gasete 1 in masca
            {
                //nodul 0 trebuie sa fie ultimul la care se ajunge
                if( la[nod_dest][i] == 0 && ( masca != ( (1<<nod_dest) +1) ) )
                    continue;

                //(masca xor (1<<nod_dest)) elimina bitul de 1 aferent nodului destintie din masca
                M[masca][nod_dest] = min( M[masca][nod_dest], Calc( la[nod_dest][i], (masca xor (1<<nod_dest)),  M) + capacitate[la[nod_dest][i]][nod_dest] );
            }
    }

    return M[masca][nod_dest];
}


int Graf::HamiltonCostMinim()
{
    //problem este NP

    // matrice folosita la memoizare ce va avea dimensiunile 2^n si n
    vector<vector<int>> M;

    //initializam matricea M
    M.resize((1<<n)+5, vector<int>(n+1, -1));

    //variabila in care se va salva costul minim al lantului hamiltonian, initial egala cu infinit(=100000000)
    int cost = 100000000;

    //vom folosi matricea capacitate deja existenta in clasa graf pentru a retine costurile arcelor

    //dimensionam matricea de costuri si o umplem cu valoarea infinit(=100000000)
    capacitate.clear();
    capacitate.resize(n, vector<int>(n, 100000000));

    //completam matricea de costuri(costurile sunt luate din listel de adiacenta)
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<arce[i].size(); ++j)
        {
            int y = arce[i][j].y;
            capacitate[i][y] = arce[i][j].distanta;
            la[y].push_back(i);
        }
    }


    //initializam lantul format doar din nodul de start(nodul 0) cu 0
    M[1][0] = 0;

    //pentru fiecare nod adiacent lui 0(noduri din care se ajunge in 0)
    //actualizam costul minim(variabila cost);

    //costul va fi minimul dintre valoarea sa actuala si costul arcului de la nodul adiacent la nodul 0
    //la care adunam costul unui drumu
    //de la nodul 0 la adiacent;

    //(1<<n)-1 masca ce are toti bitii setati la 1

    for(int v=0; v<la[0].size(); ++v)
        cost = min(cost, Calc(la[0][v], (1<<n)-1,M) + capacitate[la[0][v]][0]);

    return cost;
}


bool Graf::DfsCuplaj(int nod, vector<int>&L, vector<int>&R)
{
    //daca nodul a fost vizitat(are pereche) returnam fals
    if(vizitat[nod])
        return false;

    //marcam nodul curent ca vizitat
    vizitat[nod] = 1;

    //in prima etapa cautam in lista de adiacenta a lui nod, un nod necuplat din multimea R
    for(int i=0; i<la[nod].size(); ++i)
        if(R[la[nod][i]] == 0)
        {
            //cuplam cele doua noduri
            L[nod] = la[nod][i];
            R[la[nod][i]] = nod;
            return true;
        }

    //in a doua etapa, daca nu am gasit in R un nod liber pentru cuplaj, se cauta a se modifica un cuplaj facut anterior catre un nod
    //adiacent al nodului curent
    for(int i=0; i<la[nod].size(); ++i)
        if(DfsCuplaj(R[la[nod][i]], L, R)) //daca putem desface cuplajul(il putem inlocui cu un cuplaj nou)
            //inseamna ca pot cupla nodul actual cu nodul vecin abia eliberat
        {
            //cuplam cele doua noduri
            L[nod] = la[nod][i];
            R[la[nod][i]] = nod;
            return true;
        }

    //daca pentru actualul nod nu s-a putut gasi niciun cuplaj nou
    return false;
}


vector<pair<int,int>> Graf::CuplajMaxim(int n1, int n2)
{
    //complexitatea algoritmului este O(M*sqrt(N)), unde N reprezinta numarul total de noduri al grafului biparit
    //n1 si n2 reprezinta dimensiunile celor doua  multimi ce alcatuiesc graful bipartit

    //vectorulin care se v-a construi rezultatul
    vector<pair<int, int>> rez;

    //metoda utilizata doar la grafuri neorientate bipartite
    if(orientat == true)
    {
        cout << "Metoda CuplajMaxim este folosita doar la grafuri neorientate bipartite!\n";
        return rez;
    }

    //vectorul L retin pentru fiecare nod din multimea stanga a grafului bipartit daca este cuplat si daca da cu care nod din multimea dreapta,
    //analog si pentru vectorul R
    vector<int> L(n1+1, 0);
    vector<int> R(n2+1, 0);

    //variabila care retine daca am terminat de gasit cuplaje noi
    bool nu_e_gata = true;

    while(nu_e_gata)
    {
        nu_e_gata = false;

        //pregatim vectorul vizitat pentru apelul DfsCuplaj
        vizitat.clear();
        vizitat.resize(n1+1, 0);
        for(int i=1; i<=n1; ++i)
            if(L[i]==0) //daca nodul curent nu a fost cuplat
            {
                bool test = DfsCuplaj(i, L, R); //test ne va spune daca am gasit un cuplaj pt nodul curent
                //si in acelasi timp, apelul DfsCuplaj ne va seta cuplajul gasit
                if(test)
                    nu_e_gata = true;
            }
    }

    //construim vectorul rezultat si il returnam
    for(int i=1; i<=n1; ++i)
        if(L[i]!=0) //daca avem pereche pt nodul curent adaugam perechea in rezultat
            rez.push_back(make_pair(i,L[i]));

    return rez;
}


int main()
{
    int n, m;
    fin >> n >> m;

    Graf g(n, m, 0, 0);
    for(int i=1; i<=m; ++i)
    {
        int x,y;
        fin >> x >> y;
        g.AddEdge(x,y);
    }

    fout << g.DfsNrConexe(1);
    return 0;
}