#ifndef AF_LABORATOR1_GRAF_H
#define AF_LABORATOR1_GRAF_H

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

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.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
    vector<int> rezultat;//vectorul in care se va construi rezultatul functiilor recursive
    vector<int> tati;//vectorul de tati folosit in parcurgeri(vector utilizat in comun de metodele bfs_maxflow si Maxflow)
    vector<bool> vizitat; //vector folosita in parcurgeri pentru a retine ce noduri au fot vizitate
    vector<vector<int>> flux; //matrice in care se moreaza fluxurile dintre doua noduri adiacente din graf(utilizat in comun de metodele bfs_maxflow si Maxflow)
    vector<vector<int>> capacitate; //matrice in care se moreaza capacitatile dintre doua noduri adiacente din graf(utilizat in comun de metodele bfs_maxflow si Maxflow)
    vector<vector<int>> la; //vector cu listele de adiacenta
    vector<muchie_cost> vmc; //vector de muchii cu cost
    vector<vector<arc>> la_arce; //vector cu listele de adiacenta ale nodurilor dintr-un graf orientat(folosita pentru metodele Dijkstra si Bellman_Ford)
    bool orientat; //variabila care ne spune daca graful este orientat sau nu(daca este orientat este true altfel este false)
    bool costuri;//variabila care ne spune daca muchiile grafului au sau nu asociate costuri(daca da costuri este true altfel este false)
    void dfs_rec(int x, vector<int> & parcurgere, vector<int> & vizitat); //dfs = parcurgere dfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
    void dfs_mc(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 Muchii_critice
    void dfs_bcx(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 Biconexe
    void dfs_ctc(int x, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe, vector<bool> & vizitat);//subprogram de tip dfs folosit de metoda Componente_Tare_Conexe
    bool bfs_maxflow(int S, int D);//metoda ce implementeaza o parcurgere bfs si intoarce false daca din sursa nu se poate ajunge in destinatie, folosita in algoritmul Edmonds-Karp;
    //complexitate O(n)

public:
    Graf(int n, int m, bool orientat, bool costuri);//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)
    void Add_edge(int x, int y); //metoda de adaugare a unei muchii in graf
    void Add_edge_c(int x, int y, int c); //metoda de adaugare a unei muchii cu cost in graf
    void Add_arc(int x, int y, int d); //metoda de adaugare a unui arc cu distanta in graf
    vector<int> dfs(int x);//dfs=parcurgere dfs a grafului
    vector<int> bfs(int x);//bfs = parcurgere bfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
    vector<int> SortareTop(); //sortarea topologica a grafului(daca acesta este orientat si aciclic); afiseaza vectorul sortarii
    vector<set<int>> Biconexe(); //metoda ce afiseaza vectorul de componente biconexe(care sunt vectori de noduri) ale grafului
    vector<vector<int>> Muchii_critice(); //metoda ce afiseaza vectorul de muchii critice(care sunt vectori cu 2 elemente) ale grafului
    vector<set<int>> Componente_Tare_Conexe(); //metoda ce afiseaza vectorul de componente  tareconexe
    vector<pair<int,int>> Kruskal(int &cost_total);//metoda ce implementeaza algoritmul lui Kruskal de determinare a APM-ului
    vector<int> Dijkstra(int s); //metoda ce implementeaza algoritmul lui Dijkstra de determinare a drumurilor minime de la un nod dat
    // la toate celelalte, folosind un heap (complexitate O(m*logn))
    vector<int> BellmanFord(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 (complexitate O(m*n))
    int Maxflow(int S, int D);//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); complexitate O(n*(m^2))
    vector<vector<int>> RoyFloyd();//metoda ce implementeaza algoritmul Roy-Floyd de determinare a matricei de drumuri minime dintr-un graf;
    //complexitate O(n^3)
    int Darb();//metoda ce returneaza diametrul arborelui(disanta dintre cele mai indepartate doua frunze ale arborelui) - complexitate O(n)
    vector<int> Ciclueuler(); //metoda ce returneaza un ciclu eulerian din graf, daca acesta exista sau -1 altfel
};

#endif //AF_LABORATOR1_GRAF_H

//clasa de multimi disjuncte folosita la algoritmul lui Kruskal
class DisjointSets
{
private:
    int n; //numarul de noduri
    vector<int> rep; //vectorul de reprezentanti(conform cursului)
    vector<int> h; //vector ce va retine inaltimile arborilor

public:
    DisjointSets(int n);//constructor parametrizat care face si initializarea vectorului de preprezentanti
    int Reprezentant(int x);//metoda ce returneaza reprezentantul unui nod x dat
    void Reuniune(int x, int y);//metoda ce reuneste arborii care contin nodurile x si 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 //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:
    int n; //nr de noduri din heap
    int N; //numarul de noduri distincte din heap
    vector<arc> h; //vector de arce prin care este reprezentat heap-ul
    vector<int> pozitii; //vector ce retine pe ce pozitie in heap se afla fiecare nod x

public:
    Min_heap(int n); //constructor parametrizat pt heap
    arc pop(); //metoda care scoate minimul din heap(varful)
    void push(arc a); //metoda care insereaza in heap un arc
    void go_down(int i, int n); //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_up(int i); //metoda de deplasare in sus in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
    int poz_min(int i, int n); //metoda care obtine pozitia fiului minim al unui nod abia inserta in heap
    bool empty(); //metoda care testeaza daca heap-ul este gol
};

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)
{
    if(2*i>n) //daca nodul este frunza
        return 0;

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

}

void Min_heap::go_up(int i)
{
    if(i>1) //daca nodul nu este deja in varf
    {
        int p = i/2; //aflu parintele
        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)
{
    if(i<=n/2) //daca nodul nu este deja frunz
    {
        int m = poz_min(i,n); //aflu pozitia celui mai mic dintre fii
        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);
    la_arce.resize(n+1);

}


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

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

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

void Graf::dfs_rec(int x, vector<int> & parcurgere, vector<int> & vizitat)
{

    vizitat[x] = true;
    //std::cout << x << " ";
    parcurgere.push_back(x);
    for(int i=0; i<la[x].size(); ++i)
    {
        int y = la[x][i];

        if (vizitat[y] == false)
        {
            dfs_rec(y, parcurgere, vizitat);
            tati[y]=x;
        }
    }
}

vector<int> Graf::dfs(int x)
{
    vector<int> parcurgere;
    tati.clear();
    tati.resize(n+1);
    vector<int> vizitat(n+1, 0);
    dfs_rec(x, parcurgere, vizitat);


    return parcurgere;
}


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();
        //std::cout << x << " ";
        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);
        //cout << x << " ";
    }
    return rez;

}

void Graf::dfs_bcx(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
            dfs_bcx(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])
            dfs_bcx(i,0,moment,low,stiva, timp, biconexe, vizitat);

//    cout << "Numarul de componente biconexe: " << biconexe.size() << "\n";
//    cout<< "Componentele biconexe sunt: \n";
//    for(int i=0; i<biconexe.size(); ++i)
//    {
//        cout << i+1 << ") ";
//        for(set<int>::iterator it=biconexe[i].begin(); it!=biconexe[i].end(); ++it)
//            cout << *it << " ";
//        cout << "\n";
//    }
    return biconexe;
}

void Graf::dfs_mc(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)
        {
            dfs_mc(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::Muchii_critice()
{
    vector<vector<int>> result; //vectorul de componente biconexe
    if(orientat == true)
    { cout << "Metoda Muchii_critice este folosita doar la grafurile neorientate!\n";
        return result;
    }

    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


    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])
            dfs_mc(i,0,moment,low, timp, result, vizitat);


//    cout << "Numarul de muchii critice: " << result.size() << "\n";
//    cout << "Muchiile critice sunt: \n";
//    for(int i=0; i<result.size(); ++i)
//    {
//        cout << i+1 << ") " << result[i][0] << " " << result[i][1] <<"\n";
//    }
    return result;
}

void Graf::dfs_ctc(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)
        {
            dfs_ctc(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::Componente_Tare_Conexe()
{
    vector<set<int>> tareconexe; //vectorul de componente tare-conexe

    if(orientat == false)
    { cout << "Metoda Componente_Tare_Conexe este folosita doar la grafurile orientate!\n";
        return tareconexe;
    }
    vector<bool> vizitat(n+1);
    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<int> stiva; //stiva in care vom retine nodurile unei componente tare-conexe
    set<int> in_stack;//multimne care retine ce elemente sunt in stiva la un anumit moment

    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)
            dfs_ctc(j, moment, low, stiva, in_stack, timp, tareconexe, vizitat);

//    cout << "Numarul de componente tareconexe: "<< tareconexe.size() << "\n";
//    cout<< "Componentele tareconexe sunt: \n";
//    for(int i=0; i<tareconexe.size(); ++i)
//    {
//        cout << i+1 << ") ";
//        for(set<int>::iterator it=tareconexe[i].begin(); it!=tareconexe[i].end(); ++it)
//            cout << *it << " ";
//        cout << "\n";
//    }
    return tareconexe;
}

vector<pair<int,int>> Graf::Kruskal(int &cost_total)
{
    if(orientat == true)
    { cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile neorientate conexe!\n";
        return {};
    }

    if(costuri == false)
    { cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile 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);

    vector<muchie> rezultat;//vectorul in care vom retine muchiile APM-ului
    rezultat.resize(n-1);//APM-ul va avea exact n-1 muchii(pt ca este arbore)

    int contor = 0;//variabila care retine cate muchii au fost selectate pana la un anumit moment de timp
    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);
    //afisam rezultatul(APM-ul)
//    cout << "\n";
//    cout << "Costul total al APM-ului este: " << cost_total << "\n";
//    cout << "Numarul de muchii din APM este: " << n-1 << "\n";
//    cout << "Muchiile APM-ului sunt:\n";
    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)
{

    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<int> d(n+1, 1000000001); //vector de distante
    vector<int> t(n+1, 0); //vectorul de tati
    d[s] = 0;
    Min_heap H(n); //declaram heapul

    //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<la_arce[s].size(); ++i)
    {
        H.push(la_arce[s][i]);
        d[la_arce[s][i].y] = la_arce[s][i].distanta;
        t[la_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 in ele
    while(!H.empty())
    {
        arc ac = H.pop(); //arcul curent

        for(int i=0; i<la_arce[ac.y].size(); ++i)
        {
            int z = la_arce[ac.y][i].y; //nodul in care s-a ajuns din  nodul curent
            int nd = d[ac.y] + la_arce[ac.y][i].distanta;//noua distanta
            if(nd < d[z]) //relaxare muchie
            {
                d[z] = nd;
                t[z] = ac.y;
                H.push(arc(z,nd));
            }
        }
    }
    //cout << "Costurile drumurile minime de la nodul " << s << " la toate celelelate noduri, determinate in urma algoritmului Dijkstra sunt: ";
//    for(int i=2; i<=n; ++i)
//        if(d[i] == 1000000001)
//            cout << 0 << " ";
//        else
//            cout << d[i] << " ";
//    cout << "\n";

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


vector<int> Graf::BellmanFord(int s)
{
    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<int> d(n+1, 1000000001); //vector de distante
    vector<int> cnt(n+1, 0); //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> selectat(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> t(n+1, 0); //vectorul de tati
    d[s] = 0;
    selectat[s] = 1;
    cnt[s] = 1;

    queue<int> q; //coada in care se vor pune nodurile ale caror disante s-au modificat(pentru optimizarea algoritmului)
    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 < la_arce[u].size(); ++j)
        {
            int v = la_arce[u][j].y;
            int nd = d[u] + la_arce[u][j].distanta;// noua distanta folosita la eventuala relaxare
            if (nd < d[v]) //testare pentru relaxarea drumului
            {
                d[v] = nd;
                t[v] = u;

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

            }
        }
    }

    //cout << "Costurile drumurile minime de la nodul " << s << " la toate celelelate noduri, determinate in urma algoritmului BellmanFord sunt: ";
//    if(circuit_negativ)
//        cout << "Ciclu negativ!";
//    else{
//        for(int i=2; i<=n; ++i)
//            if(d[i] == 1000000001)
//                cout << 0 << " ";
//            else
//                cout << d[i] << " ";
//    }

    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()
{
    //doar la grafuri cu cost

    int inf = (1<<20);
    vector<vector<int>> md; //matricea drumurilor unui graf, folosita in algoritmul Roy-Floyd
    md.resize(n+1,vector<int>(n+1,inf));


    //construim matricea drumurilor din listele de adiacenta la_arce
    for(int i=1; i<=n; ++i)
        for(int j=0; j<la_arce[i].size(); ++j)
            if(la_arce[i][j].distanta!=0)
                md[i][j+1] = la_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::bfs_maxflow(int S, int D)
{

    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)
{
    //doar la grafuri orientate cu cost

    //golesc vectorul tati la fiecare parcurgere(pentru aflarea fiecarui drum de ameliorare)
    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<la_arce[i].size(); ++j)
        {
            int y = la_arce[i][j].y;
            capacitate[i][y] += la_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(bfs_maxflow(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()
{
    //doar la arbori(graf neorientat conex si aciclic)
    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()
{

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

    }

    vector<int> rezultat;
    bool mv[m+1]; //vector ce retine pt fiecare muchie daca a fost sau nu vizitata

    //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(!la_arce[nod].empty())
        {
            //extragem un vecin
            int y = la_arce[nod].back().y;
            int poz = la_arce[nod].back().distanta;
            la_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;
}

const int NMAX = 100005, MMAX = 500005;
Graf g(NMAX,MMAX,0,0);


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

    for(int i=1; i<=m; ++i)
    {
        fin >> x >> y;
        g.Add_arc(x, y, i);
        g.Add_arc(y, x, i);

    }

    vector<int> rezultat;
    rezultat = g.Ciclueuler();

    for(int i=0; i<rezultat.size(); ++i)
        fout << rezultat[i] << " ";
    return 0;
}