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

using namespace std;

//CLASA GRAPH DE BAZA

class Graph{

//DATELE MEMBRE

protected:
    int m_number_of_nodes;
    //numarul de noduri


//METODELE

public:

    //functia de citire virtuala -> implementata diferit in fiecare dintre clase
    virtual void read_graph(char *file);

    //parcurgerea in latime
    virtual vector<int> BFS(int node);

    //parcurgerea in adancime
    virtual void DFS(int node, vector<int>& visited);

    //metoda hakimi -> intoarce true daca se poate construi un graf din secventa data ca argument si false in caz contrar
    bool hakimi(vector<int> v);
};

//METODE PUBLICE

//citirea grafului simplu este o metoda virtuala implementata in fiecare dintre clasele mostenitoare

void Graph::read_graph(char *file) {
    return;
}

vector<int> Graph::BFS(int node){
    vector<int> aux;
    return aux;
}

void Graph::DFS(int node, vector<int> &visited) {
    return;
}

//Havel Hakimi: O(n^2 log n)

bool Graph::hakimi(vector<int> v){

    //daca suma gradelor nodurilor nu este para, automat nu se va putea face un graf din secventa, asa ca verificam acest lucru mai intai
    //daca vreuna din valorile din secventa este mai mare sau egala cu numarul de noduri, automat nu va putea fi epuizat gradul acelui nod si, implicit,
    //nu se va putea construi graf din secventa v, asa ca verificam si acest lucru

    int sum =0;

    for(int i = 0; i < v.size(); i++){

        if(v[i] >= v.size()) return false;

        sum = sum + v[i];
    }

    if(sum % 2 == 1) return false;

    //sortam descrescator gradele din secventa
    sort(v.begin(), v.end(), greater<int>());

    //incercam sa epuizam gradele
    while(v[0] != 0){

        //parcurgem toate nodurile si le legam(scazand gradul fiecaruia)
        for(int i = 0; i <= v[0]; i++){

            v[i]--;

            //daca se ajunge la valori negative pentru grad inseamna ca graful nu poate fi format
            if(v[i] < 0) return false;
        }
        v[0] = 0;
        sort(v.begin(), v.end(), greater<int>());
    }

    return true;
}

//CLASA GRAFURI NEORIENTATE

class Undirected_graph: protected Graph{
protected:
    vector< vector<int> > m_adjancency_list;
public:
    //citirea grafului
    void read_graph(char *file);

    //parcurgerea in adancime DFS
    void DFS(int node, vector<int>& visited);

    //numararea componentelor conexe
    int number_of_connected_components();

    //returnarea unui vector cu componentele conexe
    vector< unordered_set<int> > generate_biconnected_components();

    //gasirea muchiilor critice
    vector< vector<int> > find_critical_edges();

private:
    void DFSBiconnected(int current_node, int prec, int step, vector<int>& arrival_values, vector<int>& low_link_values,vector<unordered_set<int>>& biconnected_components,stack<pair <int, int>>& current_biconnected_components);
    void DFSCriticals(int current_node, int& step, vector<int>& visited, vector<int>& prec, vector<int>& low_link_values, vector<int>& arrival_times, vector< vector<int> >& critical_edges);
};

//METODE PUBLICE GRAFURI NEORIENTATE

void Undirected_graph::read_graph(char *file) {
    ifstream f(file);

    vector<int> aux;
    int number_edges;

    //citim numarul de noduri si numarul de muchii
    f>>this->m_number_of_nodes >> number_edges;

    //rezervam in matricea de vecini spatiu pentru numarul de noduri ale grafului
    this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);

    //citim fiecare muchie si o marcam pentru ambele capete - adaugam fiecare nod ca vecin al ceiluilalt

    for(int i = 0; i < number_edges; i++){
        int x,y;

        f >> x >> y;

        this->m_adjancency_list[x].push_back(y);
        this->m_adjancency_list[y].push_back(x);
    }
}

//DFS PE GRAFURI NEORIENTATE: O(numar de noduri + numar de muchii)

void Undirected_graph::DFS(int node, vector<int> &visited) {

    //marcam nodul curent ca vizitat

    visited[node] = 1;

    //parcurgem vecinii si pentru fiecare vecin nevizitat aplicam recursiv DFS
    for(int i = 0; i < this->m_adjancency_list[node].size(); i++){

        if(visited[ this->m_adjancency_list[node][i] ] == 0){
            DFS( this->m_adjancency_list[node][i], visited);
        }
    }
}

//NUMARUL DE COMPONENTE CONEXE INTR-UN GRAF NEORIENTAT: O(numar noduri + numar muchii)

int Undirected_graph::number_of_connected_components() {

    //numarul componentelor conexe il vom tine in nr
    int number = 0;

    //initial toate nodurile sunt nevizitate
    vector<int> visited;
    visited.assign(m_number_of_nodes + 1, 0);

    //pentru fiecare nod nevizitat parcurgem din copil in copil prin DFS; de fiecare data cand dam de un node nevizitat inseamna ca avem o noua componenta conexa
    for(int node = 1; node <= this->m_number_of_nodes; node++){
        if(visited[node] == 0){
            number++;
            DFS(node, visited);
        }
    }

    return number;
}

//NUMARUL DE COMPONENTE BICONEXE DIN GRAFUL NEORIENTAT: O(numar de noduri + numar de muchii)

vector< unordered_set<int> >Undirected_graph::generate_biconnected_components(){

    vector<unordered_set<int>> biconnected_components;
    stack<pair <int, int>> current_biconnected_component;

    vector<int> arrival_value;
    vector<int> low_link_values;

    //initializam timpii de sosire cu 0 pentru fiecare nod si rezervam spatiu pentru vectorul cu nivelul cel mai de sus accesibil pentru fiecare nod al grafului

    arrival_value.assign(this->m_number_of_nodes + 1, -1);
    low_link_values.resize(this->m_number_of_nodes + 1);

    //facem DFS

    DFSBiconnected(1,0,0,arrival_value,low_link_values,biconnected_components,current_biconnected_component);

    //returnam vectorul de componente biconexe modificat in urma DFS-ului

    return biconnected_components;
}

//GASIREA MUCHIILOR CRITICE: O(numar noduri + numar muchii)

vector< vector<int> > Undirected_graph::find_critical_edges() {

    int current_arrival_time = 0;
    vector< vector<int> > critical_edges;

    vector<int> visited;
    vector<int> prec;
    vector<int> low_link_values;
    vector<int> arrival_times;

    //initializam toate nodurile ca fiind nevizitate
    visited.assign(m_number_of_nodes + 1, 0);

    //rezervam spatiu pentru vectorul de precedenti ai fiecarui nod din graf
    prec.resize(m_number_of_nodes + 1);

    //rezervam loc pentru vectorul in care pentru fiecare nod din graf retinem cel mai de sus nivel la care poate ajunge acel nod
    low_link_values.resize(m_number_of_nodes + 1);

    //initializam timpii de ajungere la fiecare nod din graf
    arrival_times.assign(m_number_of_nodes + 1, -1);

    //parcurgem nodurile grafului si, pentru fiecare nod nevizitat, facem DFS

    for(int i = 1; i <= m_number_of_nodes; i++){

        if(visited[i] == 0){
            DFSCriticals(i, current_arrival_time, visited, prec, low_link_values, arrival_times, critical_edges);
        }
    }

    return critical_edges;
}

//METODE PRIVATE GRAFURI NEORIENTATE

//DFS-ul pe care il folosim la detereminarea componentelor biconexe

void Undirected_graph::DFSBiconnected(int current_node, int prec, int step, vector<int>& arrival_values, vector<int>& low_link_values, vector<unordered_set<int>>& biconnected_components, stack<pair <int, int>>& current_biconnected_components){

    //marcam ca vizitat nodul curent
    arrival_values[current_node] = step;

    //momentan nivelul minim de intoarcere e nivelul curent, adica pasul
    low_link_values[current_node] = step;

    //parcurgem vecinii nodului curent
    for(int i = 0; i < this->m_adjancency_list[current_node].size(); i++){

        int neighbor = this->m_adjancency_list[current_node][i];

        if(neighbor != prec){
            //verificam pe ce fel de muchie suntem
            //daca vecinul curent a mai fost vizitat inseamna ca am dat de o muchie de intoarcere, altfel suntem pe o muchie in jos

            if(arrival_values[neighbor] == -1){

                //am dat de o noua muchie din componenta biconexa curenta, asa ca o adaugam in stiva
                current_biconnected_components.push(make_pair(current_node, neighbor));

                //apelam DFS pentru vecinul curent
                DFSBiconnected(neighbor, current_node, step + 1,arrival_values,low_link_values,biconnected_components,current_biconnected_components);

                //verificam daca atunci cand ne am dus mai departe in graf
                // am dat de o muchie de intoarcere care ne duce mai sus decat ne ducea nodul acesta inainte

                if(low_link_values[current_node] > low_link_values[neighbor]){
                    low_link_values[current_node] = low_link_values[neighbor];
                }

                //verificam daca am ajuns la finalul componentei biconexe

                if(low_link_values[neighbor] >= arrival_values[current_node]){
                    //trebuie sa adaugam noua componenta biconexa in vectorul de componenete biconexe
                    //si sa golim stiva cu muchiile componentei biconexe curente
                    unordered_set<int> aux;
                    int aux1, aux2;

                    //ne formam in aux componenta biconexa si apoi o adaugam in vectorul de componente biconexe

                    do{

                        aux1 = current_biconnected_components.top().first;
                        aux2 = current_biconnected_components.top().second;

                        aux.insert(aux1);
                        aux.insert(aux2);

                        current_biconnected_components.pop();

                    } while (aux1 != current_node || aux2 != neighbor);

                    biconnected_components.push_back(aux);
                }
            }else{
                //avem o muchie de intoarcere, trebuie sa verificam daca nu cumva duce mai sus, caz in care sa actualizam nivelul minim la care se poate ajunge din nodul curent

                if(low_link_values[current_node] > arrival_values[neighbor]){
                    low_link_values[current_node] = arrival_values[neighbor];
                }
            }
        }
    }
}

//DFS-ul pe care il folosim in gasirea muchiilor critice

void Undirected_graph::DFSCriticals(int current_node, int &step, vector<int> &visited, vector<int> &prec,
                                    vector<int> &low_link_values, vector<int> &arrival_times,
                                    vector<vector<int>> &critical_edges) {

    //marcam nodul ca vizitat in vectorul visited, actualizam timpul lui de ajungere iar low link value momentan e fix timpul de ajungere
    visited[current_node] = 1;
    arrival_times[current_node] = step;
    low_link_values[current_node] = step;

    //crestem timpul de ajungere pentru urmatorul DFS
    step++;

    //parcurgem vecinii nodului
    for(int i = 0; i < m_adjancency_list[current_node].size(); i++){

        int neighbor = m_adjancency_list[current_node][i];

        //pentru fiecare vecin nevizitat, ii actualizam precedentul ca fiind nodul ai carui vecini ii parcurgem si intram in parcurgerea vecinilor vecinului
        if (visited[neighbor] == 0){

            prec[neighbor] = current_node;

            DFSCriticals(neighbor, step, visited, prec, low_link_values, arrival_times, critical_edges);

            //la iesirea din DFS incercam sa minimizam low link value pentru nodul curent, in cazul in care vecinul poate ajunge la un node mai indepartat
            if(low_link_values[current_node] > low_link_values[neighbor]){

                low_link_values[current_node] = low_link_values[neighbor];
            }

            //in cazul in care este o muchie critica, o adaugam in vectorul de muchii critice
            if (low_link_values[neighbor] > arrival_times[current_node]){

                critical_edges.push_back({current_node, neighbor});
            }
        }
        else{
            //pentru fiecare vecin deja vizitat incercam sa minimzam low link value pentru nodul nostru
            if (neighbor != prec[current_node]){

                if(low_link_values[current_node] > arrival_times[neighbor]){

                    low_link_values[current_node] = arrival_times[neighbor];
                }
            }
        }
    }
}

//CLASA UNORIENTHED GRAPH BIPARTIT
class Unoriented_bipartite_graph: Undirected_graph{
private:
    int m_number_of_left_nodes;

public:
    //citirea grafului
    void read_graph(char *file);

    vector<pair<int, int>> hopcroft_karp();

private:
    bool DFS(int node, vector<int>& left_pair, vector<int>& right_pair, vector<int>& visited);
};

//METODE GRAF NEORIENTAT BIPARTIT

void Unoriented_bipartite_graph::read_graph(char *file) {
    ifstream f(file);
    int number_of_right_nodes, number_of_edges;

    //citim numarul de noduri din stanga si din dreapta
    f >> m_number_of_left_nodes >> number_of_right_nodes;

    //numarul de noduri ale grafului va fi suma
    m_number_of_nodes = m_number_of_left_nodes + number_of_right_nodes;

    //citim numarul de muchii
    f >> number_of_edges;

    //initializam matricea de vecini cu numaruk de noduri din stanga ale grafului nostru, deoarece matricea va retine vecinii din dreapta ai nodurilor din stanga

    m_adjancency_list.assign(m_number_of_left_nodes + 1, vector<int>());

    //citim muchie cu muchie si o pe fiecare adaugam in matricea de vecini
    for(int i = 0; i < number_of_edges; i++){
        int x, y;

        f >> x >> y;

        m_adjancency_list[x].push_back(y);
    }
}

vector<pair<int, int>> Unoriented_bipartite_graph::hopcroft_karp() {
    vector< pair<int,int> > maximum_matching;

    vector<int> right_pair;
    vector<int> left_pair;
    vector<int> distances;
    vector<int> visited;

    //initializam vectorul de perechi din dreapta pentru numarul de noduri din stanga; cand valoarea e -1, inseamna ca acel nod nu are pereche in dreapta
    right_pair.assign(m_number_of_left_nodes + 1, -1);

    //initializam vectorul de perechi din stanga pentru numarul de noduri din dreapta; cand valoarea e -1, inseamna ca acel nod nu are pereche in stanga
    left_pair.assign(m_number_of_nodes - m_number_of_left_nodes + 2, -1);

    //initializam vectorul de distante pentru numarul de noduri din stanga
    distances.assign(m_number_of_left_nodes + 1, 0);

    //vom tot actualiza cuplajul maxim atata timp cat avem un lant inca negasit

    //vom retine intr-o variabila daca mai avem lanturi proaspat gasite sau nu; ne vom opri cand nu mai gasim niciun lant
    int enough = 0;

    while(enough == 0){

        //pornim cu ideea ca nu vom mai gasi lant
        enough = 1;

        //reinitiliazam toate nodurile ca neviyitate, intrucat incepem cu un nou lant
        visited.assign(m_number_of_nodes + 1, 0);

        //cautam printre nodurile din stanga un nod care nu are inca pereche
        for(int i = 1; i <= m_number_of_left_nodes; i++){

            //testam daca nodul are pereche
            if(right_pair[i] == -1){

                //incercam sa creem un lant din acest nod fara pereche;
                if(this->DFS(i,left_pair,right_pair, visited)){

                    //daca am reusit, atunci marcam ca am gasit un lant
                    enough = 0;
                }
            }
        }
    }

    //formam cuplajul-rezultat: pentru toate nodurile care au pereche in dreapta, inseamna ca fac parte din cuplaj asa ca le adaugam in vectorul de perechi
    //impreuna cu perechea lor din dreapta

    for(int i = 1; i <= m_number_of_left_nodes; i++){

        if(right_pair[i] != -1){
            maximum_matching.push_back(make_pair(i, right_pair[i]));
        }
    }

    return maximum_matching;
}

//METODE PRIVATE GRAF NEORIENTAT BIPARTIT

bool Unoriented_bipartite_graph::DFS(int node, vector<int>& left_pair, vector<int>& right_pair, vector<int>& visited) {

    //testam daca nodul a mai fost vizitat in cuplajul pe care incercam sa il facem
    if(visited[node] != 0){
        return 0;
    }

    //marcam nodul ca vizitat

    visited[node] = 1;

    //parcurgem vecinii nodului si, daca gasim printre ei unul care nu are pereche in stanga, il unim cu nodul nostru
    for(int i = 0; i < m_adjancency_list[node].size(); i++){
        int neighbor;

        //luam vecinul
        neighbor = m_adjancency_list[node][i];

        //verificam daca nodul nu are pereche in stanga
        if(left_pair[neighbor] == -1){

            //daca vecinul nu are deja pereche in stanga, il cuplam cu nodul nostru din stanga, marcandu-le amandorura noua pereche in vectorul corespunzator fiecaruia
            right_pair[node] = neighbor;
            left_pair[neighbor] = node;

            //returnam 1 pentru ca am avut succes in a construi un nou lant din nodul dat
            return 1;
        }
    }

    //daca nu am gasit niciun vecin care sa nu aiba pereche in stanga, inseamna ca e posibil sa trebuiasca sa legam nodul de un lant deja existent, nu doar de un alt nod

    //parcurgem vecinii si, daca gasim un vecin din care avem un lant, sudam nodul nostru de lantul respectiv, prin cuplarea nodului cu vecinul din care porneste lantul
    for(int i = 0; i < m_adjancency_list[node].size(); i++){
        int neighbor;

        //luam vecinul
        neighbor = m_adjancency_list[node][i];

        //verificam daca vecinul face parte dintr-un lant
        if(DFS(left_pair[neighbor],left_pair, right_pair, visited)){

            //in cazul in care DFS a returnat 1 si vecinul face parte dintr-un lant, alipim nodul nostru la lantul respectiv <=> cuplam nodul nostru cu vecinul
            //si returnam 1 pentru ca am reusit sa obtinem un lant

            left_pair[neighbor] = node;
            right_pair[node] = neighbor;

            return 1;
        }

    }

    //returnam esecul: nu mai putem forma lant din nodul dat in niciun fel

    return 0;
}

//CLASA ORIENTED GRAPH

class Directed_graph: protected Graph{
protected:
    vector< vector<int> > m_adjancency_list;

public:
    void read_graph(char *file);
    int read_graph_with_starting_node(char *file);
    vector<int> BFS(int source);
    vector<vector<int>> create_strongly_connected_components();
    void tarjan(int node,stack<int>& current_component_stack,vector<int>& is_in_stack,vector<int>& arrival_values, int& current_arrival_value, vector<int>& low_link_values, vector<vector<int>>& strongly_connected_components);
    stack<int> topological_sort();

private:
    void DFS_topological_sort(int node, stack<int>& sort, vector<int>& visited);
};

//METODE PUBLICE ORIENTED GRAPHS

//citirea grafului orientat (fara costuri)
void Directed_graph::read_graph(char *file) {

    ifstream f(file);

    vector<int> aux;
    int number_edges;

    //citim numarul de noduri si numarul de muchii
    f >> m_number_of_nodes >> number_edges;

    //rezervam in matricea de vecini spatiu pentru numarul de noduri ale grafului

    this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);

    //citim fiecare muchie si o adaugam in lista de adiacenta, prin adagarea vecinului nodului din care porneste muchia

    for(int i = 0; i < number_edges; i++){
        int x,y;

        f>>x>>y;

        this->m_adjancency_list[x].push_back(y);
    }
}

//citirea grafului orientat (fara costuri) cu node de pornire

int Directed_graph::read_graph_with_starting_node(char *file) {

    ifstream f(file);

    vector<int> aux;
    int number_edges, source;

    //citim numarul de noduri, numarul de muchii si nodul de pornire
    f >> this->m_number_of_nodes >> number_edges >> source;

    //reyervam spatiu in matricea de vecini pentru numarul de noduri ale grafului
    this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);

    //parcurgem fiecare muchie si o adaugam in lista de adiacenta, prin adaugarea vecinului la nodul din care porneste muchia

    for(int i=0; i<number_edges; i++){
        int x,y;

        f >> x >> y;

        this->m_adjancency_list[x].push_back(y);
    }
    return source;
}

//BFS PE GRAFURI ORIENTATE -> O(numar noduri + numar muchii)

//BFS(int nod) -> returneaza un vector in care pe pozitia i se afla numarul minim de arce ce trebuie parcurse de la sursa data nod pana la nodul i

vector<int> Directed_graph::BFS(int source) {
    //initializam vectorul de distances minime de la nodul sursa la fiecare nod; initial toate distantele sunt 0

    vector<int> distances;
    distances.assign(this->m_number_of_nodes + 1, 0);

    int curent;

    //folosim o coada in care vom pune nodurile pe masura ce le parcurgem
    queue<int> current_nodes;

    //initial toate nodurile sunt nevizitate, asa ca initializam visited[orice nod] = 0
    vector<int> visited;
    visited.assign(this->m_number_of_nodes + 1, 0);

    //adaugam nodul sursa in coada si il marcam ca si vizitat
    current_nodes.push(source);
    visited[source] = 1;

    //actualizam vectorul de distances pentru nodul curent cu distanta pana la el, adica 1
    distances[source] = distances[source] + 1;

    //facem BFS-ul; cat timp mai avem noduri de parcurs in coada, luam cate un nod din coada si ii parcurgem vecinii;
    //pentru fiecare vecini nevizitat, actualizam distanta pana la el, il marcam ca si vizitat si il adaugam in coada cu noduri de vizitat, urmand sa facem
    //aceiasi pasi si pentru el, dar abia atunci cand va veni randul lui in coada
    while( !current_nodes.empty() ){

        curent = current_nodes.front();

        //parcurgem vecinii nodului curent si verificam pentru fiecare daca este vizitat

        for(int i=0; i < this->m_adjancency_list[curent].size(); i++){

            if(visited[ this->m_adjancency_list[curent][i] ] == 0){

                //nodurile nevizitate se adauga la finalul cozii de parcurs

                current_nodes.push(this->m_adjancency_list[curent][i] );

                //actualizam distanta catre vecinul nodului curent; noua distanta este distanta cu care am ajuns pana la nodul curent + 1

                distances[ current_nodes.back() ] = distances[curent] + 1;

                //marcam vecinul ca vizitat

                visited[ this->m_adjancency_list[curent][i] ] = 1;
            }
        }

        //am terminat cu nodul curent, il scoatem din coada
        current_nodes.pop();
    }

    //scadem cu 1 fiecare distanta din vectorul de distante

    for(int i = 1; i <= this->m_number_of_nodes; i++){

        distances[i]--;
    }

    return distances;
}

//GASIREA COMPONENTELOR TARE CONEXE

vector< vector<int> >Directed_graph::create_strongly_connected_components() {

    vector<vector<int>> strongly_connected_components;

    //initializam stiva in care vom retine componenta tare conexa curenta pe care o formam; aceasta va ajunge dupa in vectorul de componente tare conexe

    stack<int> current_component;

    //initializam timpul de ajungere; initial 0

    int current_arrival_time = 0;

    //initializam vectorul care retine pe fiecare pozitie i 0 daca nodul i este in stva cu componenta tare conexa curenta si 0 daca nodul i nu este in ea

    vector<int> is_in_stack;
    is_in_stack.assign(this->m_number_of_nodes + 1, 0);

    //initializam vectorul cu timpii de ajungere la fiecare nod: initial -1 pentru ca nu am vizitat niciun nod inca

    vector<int> arrival_values;
    arrival_values.assign(this->m_number_of_nodes + 1, -1);

    //rezervam loc pentru vectorul care retine pe pozitia i cel mai de sus nivel la care se poate ajunge din i

    vector<int> low_link_values;
    low_link_values.resize(this->m_number_of_nodes + 1);

    //parcurgem nodurile grafului si, pentru fiecare nod care nu a fost inca vizitat(deci timpul de ajungere la el este -1) facem tarjan

    for(int i=1; i<=this->m_number_of_nodes; i++){
        if(arrival_values[i] == -1){
            tarjan(i, current_component, is_in_stack, arrival_values, current_arrival_time, low_link_values, strongly_connected_components);
        }
    }

    return strongly_connected_components;
}

//TARJAN: O(numar de noduri + numar de muchii)

void Directed_graph::tarjan(int node, stack<int> &current_component_stack, vector<int> &is_in_stack,
                            vector<int> &arrival_values, int &current_arrival_value, vector<int> &low_link_values,
                            vector<vector<int>> &strongly_connected_components) {

    //adaugam nodul in componenta tare conexa curenta, adica in current_component_stack
    current_component_stack.push(node);

    //marcam nodul ca facand parte din componenta tare conexa curenta prin vectorul is_in_stack
    is_in_stack[node] = 1;

    //marcam nodul ca vizitat, atribuindu-i chiar timpul de ajungere
    arrival_values[node] = current_arrival_value;
    //valoarea low Link momentan este tot nivelul nodului curent

    low_link_values[node] = current_arrival_value;

    //marim timpul de ajungere pentru urmatorul step
    current_arrival_value++;

    //parcurgem vecinii nodului curent, facand un DFS

    for(int i=0; i<this->m_adjancency_list[node].size(); i++){
        int neighbor = this->m_adjancency_list[node][i];

        //verificam daca vecinul curent nu a fost inca vizitat
        if(arrival_values[neighbor] == -1){
            //aplicam tarjan pe nodul curent

            tarjan(neighbor, current_component_stack, is_in_stack, arrival_values, current_arrival_value, low_link_values, strongly_connected_components);

            //la iesire incercam sa minimizam valoarea low link a nodului curent, daca vecinul la care suntem a facut in timpul tarjan-ului una mai mica
            if(low_link_values[neighbor] < low_link_values[node]){
                low_link_values[node] = low_link_values[neighbor];
            }

        }else{  //daca vecinul a fost deja vizitat
            //verificam daca vizitarea s-a produs in cadrul componentei tare conexe curente

            if(is_in_stack[neighbor] == 1){
                //incercam sa minimizam valoarea low link a nodului curent, in cazul in care vecinul curent ajunge la un node mai indepartat decat valoarea noastra curenta

                if(low_link_values[neighbor] < low_link_values[node]){
                    low_link_values[node] = low_link_values[neighbor];
                }
            }
        }
    }
    //verificam daca nodul curent inchide o componenta tare conexa
    if(arrival_values[node] == low_link_values[node]){
        //trebuie sa mutam componenta tare conexa curenta din stiva in vectorul cu toate componentele tare conexe din graf
        vector<int> aux;
        int aux_node;

        do{

            aux_node = current_component_stack.top();

            aux.push_back(aux_node);

            current_component_stack.pop();
            is_in_stack[aux_node] = 0;

        }while(aux_node != node);

        strongly_connected_components.push_back(aux);
    }
}

//SORTAREA TOPOLOGICA: O(numar noduri + numar de muchii)

stack<int> Directed_graph::topological_sort() {
    vector<int> visited;
    stack<int> sort;

    //initial toate nodurile sunt nevizitate

    visited.assign(m_number_of_nodes + 1, 0);

    //parcurgem toate nodurile grafului si, pentru fiecare nod nevizitat inca, aplicam DFS

    for(int i = 1; i <= this->m_number_of_nodes; i++){

        if(visited[i] == 0){

            DFS_topological_sort(i, sort, visited);
        }
    }

    return sort;
}

//METODE PRIVATE ORIENTED GRAPHS

//DFS-ul pe care il folosim in sortarea topologica

void Directed_graph::DFS_topological_sort(int node, stack<int> &sort, vector<int>& visited) {

    //marcam nodul la care am ajuns ca vizitat

    visited[node] = 1;

    //parcurgem vecinii nodului curent si, daca vecinul este nevizitat, ii aplicam DFS

    for(int i = 0; i < this->m_adjancency_list[node].size(); i++){

        int neighbor = this->m_adjancency_list[node][i];

        if(visited[neighbor] == 0){

            DFS_topological_sort(neighbor, sort, visited);
        }
    }

    //adaugam nodul curent in stiva care retine nodurile pe masura ce ajungem la ele

    sort.push(node);
}

//CLASA UNORIENTED GRAPH WITH COSTS

class Unoriented_graph_with_costs:Graph{
private:
    vector< vector< pair <int,int> > > m_adjancency_list;
public:
    //citirea grafului sub forma listei de vecini
    void read_graph(char *file);

    //algoritmul lui prim->returneaza arborele partial de cost minim si, prin parametrul primit, returneaza si costul
    vector< pair<int,int> > prim(int& cost_APM);
private:
    //introducerea unui node in APM
    void introduce_in_APM(int node, vector<int>& distances, vector<int>& neighbors);

    //introducerea unui node in heap-ul de minim
    void introduce_in_min_heap(int node, vector<int>& heap, vector<int>& positions, vector<int> distances);

    //urcarea in heap-ul de minim
    void pop(int index, vector<int>& heap, vector<int>& poz, vector<int>& distances);

    //extragerea unui node din heap-ul de minim
    int extract_root_min_heap(vector<int>& heap,vector<int>& poz, vector<int> distances);

    //coborarea in heap-ul de minim
    void push(int index, vector<int>& heap, vector<int>& poz, vector<int>& distances);
};

//METODE PUBLICE UNORIENTED GRAPHS WITH COSTS

void Unoriented_graph_with_costs::read_graph(char *file) {

    fstream f(file);
    vector< pair <int, int> > aux;
    int number_of_edges;

    //citim numarul de noduri

    f>>this->m_number_of_nodes;

    //initializam matricea de vecini pentru numarul de noduri dat

    this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);

    //citim numarul de muchii si apoi fiecare muchie, si pentru fiecare node ii adaugam vecinul in vectorul de vecini corespunzator in matricea de vecini

    f >> number_of_edges;

    for(int i = 0; i < number_of_edges; i++){
        int x,y,cost;

        f >> x >> y >> cost;

        m_adjancency_list[x].push_back(make_pair(y, cost));
        m_adjancency_list[y].push_back(make_pair(x, cost));
    }

}

//ALGORITMUL LUI PRIM: O(m * log n), unde m este numarul de muchii si n este numarul de noduri

vector< pair<int,int> >Unoriented_graph_with_costs::prim(int &cost_APM) {

    vector<pair<int,int>> APM_edges;

    vector<int> vec;
    vector<int> positions;
    vector<int> distances;
    vector<int> heap;


    //initializam vectorul de distante cu infinit pentru fiecare node, vectorul de vecini ai fiecarui node cu 0, vectorul de pozitii al fiecarui node in heap cu 0
    // si heap-ul in care vom pune nodurile

    distances.assign(this->m_number_of_nodes + 1, 200000200);

    vec.assign(this->m_number_of_nodes + 1, 0);
    positions.assign(this->m_number_of_nodes + 1, 0);
    heap.push_back(0);

    //pornim de la primul node: initial distanta pana la primul node este 0; introducem nodul in APM;

    distances[1] = 0;

    introduce_in_APM(1, distances, vec);

    //luam toate nodurile si le introducem in heap-ul de minim; practic, radacina heap-ului va fi

    for(int i = 2; i <= this->m_number_of_nodes; i++){
        introduce_in_min_heap(i, heap, positions, distances);
    }

    //pentru fiecare nod din graf, luam nodul cu distanta minima (adica radacina heap-ului de minim), il adaugam in apm, actualizam costul, adaugam muchia
    //care pleaca din radacina in vectorul de muchii ale apm-ului si apoi parcurgem vecinii radacinii si scoatem vecinul din heap-ul de minim daca acesta exista

    for(int i = 1; i < this->m_number_of_nodes; i++){
        int root;

        root = extract_root_min_heap(heap, positions, distances);

        introduce_in_APM(root, distances, vec);

        cost_APM = cost_APM + distances[root];

        APM_edges.push_back(make_pair(root, vec[root]));

        for(int j = 0; j < this->m_adjancency_list[root].size(); j++){
            int nod;
            nod = this->m_adjancency_list[root][j].first;
            if(positions[nod]) pop(positions[nod], heap, positions, distances);
        }
    }

    return APM_edges;
}

//METODE PRIVATE UNORIENTED GRAPH WITH COSTS

//introducerea unui nod in apm in algoritmul lui prim

void Unoriented_graph_with_costs::introduce_in_APM(int node, vector<int>& distances, vector<int>& neighbors) {

    //parcurgem vecinii nodului dat; pentru fiecare vecin, incercam sa minimizam distanta;

    for(int i = 0; i < this->m_adjancency_list[node].size(); i++){

        int neighbor, cost;

        neighbor = this->m_adjancency_list[node][i].first;
        cost = this->m_adjancency_list[node][i].second;

        //incercam sa minimizam distanta catre vecinul curent: in cazul in care distanta pana la vecin stiuata pana in acest moment este mai mare decat
        // distanta pe care o obtinem mergand prin muchia de la nodul nostru la vecin, atunci actualizam distanta pana la vecin cu costul muchiei
        //de la nodul nostru la vecin; in cazul in care s-a intamplat acest lucru, inseamna ca noul precedent al vecinului curent este nodul nostru
        //asa ca, marcam acest lucru in vectorul neighbors

        distances[neighbor] = min(distances[neighbor], cost);

        if(distances[neighbor] == cost) neighbors[neighbor] = node;
    }
}

//introducerea unui nod in heap-ul de minim

void Unoriented_graph_with_costs::introduce_in_min_heap(int node, vector<int>& heap, vector<int>& poz, vector<int> distances) {
    //adaugam nodul la sfarsitul heap-ului
    heap.push_back(node);
    poz[node] = heap.size() - 1;

    //urcam nodul in heap acolo unde ii este pozitia de drept

    pop(heap.size() - 1, heap, poz, distances);
}

//eliminarea unui nod din heap-ul de minim

void Unoriented_graph_with_costs::pop(int index, vector<int>& heap, vector<int>& position_in_heap, vector<int>& distances) {

    //cat timp n-am ajuns la radacina heap-ului si inca nodul mai poate urca, adica distanta fata de el e mai mica decat distanta fata de tatal lui,urcam in heap

    while(index > 1 && distances[ heap[index] ] < distances[ heap[index / 2] ]){

        //urcarea presupune ca interschimbam in heap nodul cu tatal si pozitiile nodului si a tatalui in vectorul pozitii

        swap(heap[index], heap[index / 2]);
        swap(position_in_heap[ heap[index] ], position_in_heap[ heap[index / 2] ]);

        index = index / 2;
    }
}

//extragerea radacinii din heap-ul de minim

int Unoriented_graph_with_costs::extract_root_min_heap(vector<int>& heap,vector<int>& poz, vector<int> distances) {
    int root;

    //luam radacina si o punem la finalul heap-ului

    root = heap[1];

    swap(heap[1],heap[ heap.size() - 1 ]);
    swap(poz[ heap[1] ], poz[ heap[ heap.size() - 1 ] ]);

    //eliminam radacina din heap

    heap.pop_back();

    //reparam heap-ul

    push(1, heap, poz, distances);

    //actualizam vectorul de pozitii cu 0 in pozitia radacinii, deoarece nodul nu mai exista in heap

    poz[root] = 0;

    return root;
}

//adaugarea in heap-ul de minim

void Unoriented_graph_with_costs::push(int index, vector<int>& heap, vector<int>& poz, vector<int>& distances) {

    //cat timp nu am ajuns la finalul heap-ului pe ramura din stanga / dreapta si cat timp nodul mai poate coborî, adică distanţa fata de nodul curent e mai mare
    //decat distanta fata de fiul din stanga/dreapta

    while((index * 2 <= heap.size() - 1 && distances[ heap[index] ] > distances[ heap[index * 2] ]) ||
          (index * 2 + 1 <= heap.size() - 1 && distances[ heap[index] ] > distances[ heap[index * 2 + 1] ])){

        //comparam cei 2 fii si mergem pe cel spre care distanta e mai mica si interschimbam nodul cu fiul corespunzator

        if(distances[heap[index * 2]] < distances[heap[index * 2 + 1]] || index * 2 + 1 > heap.size() - 1){

            swap(heap[index], heap[index * 2]);
            swap(poz[heap[index]], poz[heap[index * 2]]);
            index = index * 2;

        }else{

            swap(heap[index], heap[index * 2 + 1]);
            swap(poz[heap[index]], poz[heap[index * 2 + 1]]);
            index = index * 2 + 1;
        }

    }
}

//CLASA ORIENTED GRAPH WITH COSTS

class Oriented_graph_with_costs:Graph{
private:
    vector< vector< pair<int,int> > > m_adjacency_list;
    vector< vector<int> > m_neighbors;
    vector< vector<int> > m_costs_matrix;
public:
    //citirea grafului
    void read_graph(char *file);

    //citirea grafului cu matricea de costuri
    void read_graph_with_costs_matrix(char *file);

    //citirea matricei de costuri a grafului
    void read_costs_matrix(char *file);

    //getter pentru matricea de costuri
    vector< vector<int> > get_costs_matrix();

    //metoda dijkstra -> returneaza un vector in care pe fiecare pozitie i este distanta minima de la nodul dat ca argument la nodul i
    vector<int> dijkstra(int source);

    //metoda bellman-ford -> primeste matricea de costuri si returneaza matricea de drumuri
    vector< vector<int> > bellman_ford(vector< vector<int> > costs_matrix);

    //metoda hamilton -> returneaza costul ciclului hamiltonian de cost minim; daca graful nu este hamiltonian, returneaza -1
    int hamilton();
};

//METODE PUBLICE GRAFURI ORIENTATE CU COSTURI

void Oriented_graph_with_costs::read_graph(char *file) {
    fstream f(file);
    vector< pair<int,int> > aux;
    int number_of_edges;

    //citim numarul de noduri si initializam lista de vecini cu numarul de noduri

    f>>m_number_of_nodes;

    m_adjacency_list.assign(m_number_of_nodes + 1, aux);

    //citim numarul de muchii si apoi fiecare muchie, adaugand vecinul fiecarui node in vectorul lui de vecini din matricea de  vecini

    f >> number_of_edges;

    for(int i = 0; i < number_of_edges; i++){
        int x,y,cost;

        f >> x >> y >> cost;

        this->m_adjacency_list[x].push_back(make_pair(y,cost));
    }
}

void Oriented_graph_with_costs::read_costs_matrix(char *file) {

    ifstream f(file);
    vector<int> aux;

    //citim numarul de noduri si initializam matricea de costuri cu numarul de noduri dat

    f >> this->m_number_of_nodes;

    m_costs_matrix.push_back(aux);

    //formam matricea de costuri

    for(int i = 1; i <= this->m_number_of_nodes; i++){

        //citim linia corespunzatoare nodului curent i in matricea de costuri

        vector<int> linie;
        //punem pe pozitia 0 valoarea 0 pentru ca noi lucram cu matricea de costuri incepand de pe pozitia 1
        linie.push_back(0);

        //citim fiecare valoare care este costul de a ajunge de la nodul i la nodul j si o punem pe pozitia linie[j]

        for(int j = 1; j <= this->m_number_of_nodes; j++){
            int val;
            f >> val;
            linie.push_back(val);
        }

        //adaugam linia nodului i in matrice

        m_costs_matrix.push_back(linie);
    }
}

void Oriented_graph_with_costs::read_graph_with_costs_matrix(char *file) {

    ifstream f(file);

    vector<int> aux;

    int number_of_edges;

    //citim numarul de noduri si numarul de muchii
    f >> m_number_of_nodes >> number_of_edges;

    //initializam matricea de costuri si matricea de adiacenta

    m_neighbors.assign(m_number_of_nodes + 1, aux);

    aux.assign(m_number_of_nodes + 1, 100000000);
    m_costs_matrix.assign(m_number_of_nodes + 1, aux);


    //citim fiecare muchie si costul acesteia si o introducem in graf
    for(int i = 0; i < number_of_edges; i++){

        int x, y, c;

        f >> x >> y >> c;
        m_neighbors[y].push_back(x);
        m_costs_matrix[x][y] = c;
    }
}

vector< vector<int> > Oriented_graph_with_costs::get_costs_matrix() {
    return this->m_costs_matrix;
}

vector<int> Oriented_graph_with_costs::dijkstra(int source) {

    vector<int> paths;

    //initializam vectorul de distante minime cu infinit pe fiecare pozitie corepsunzatoare fiecarui node

    paths.assign(this->m_number_of_nodes + 1, 200000200);

    //pornim de la nodul dat ca argument: paths[nodul surs] = 0: distanta de la nodul sursa la el insusi este 0

    paths[source] = 0;

    //tree este un arbore care retine perechi de forma (cost de a ajunge de la nodul sursa la nodul i, nodul i);
    // introducem in arbore prima pereche: distanta de la nodul sursa la acesta(adica 0) si nodul sursa

    set<pair<int,int>> tree;
    tree.insert(make_pair(0, source));

    //cat timp arborele nu e gol

    while(!tree.empty()){

        //extragem din arbore nodul si costul de la radacina

        int nod,cost;

        nod = tree.begin()->second;
        cost = tree.begin()->first;
        tree.erase(tree.begin());

        //parcurgem vecinii nodului de la radacina arborelui si incercam minimizarea distantelor

        for(int i = 0; i < this->m_adjacency_list[nod].size(); i++){
            int neighbor, cost_neighbor;

            neighbor = this->m_adjacency_list[nod][i].first;
            cost_neighbor = this->m_adjacency_list[nod][i].second;

            //daca distanta de la nodul sursa pana la vecin pe care o aveam pana la acest moment este mai mare decat
            //distanta pe care am obtine-o prin nodul curent cu drumul pana la acesta + costul muchiei de la acesta la vecin
            //atunci minimizam distanta catre vecin; in cazul in care este primul drum pe care il gasim catre vecin, scoatem din arbore perechea corespunzatoare vecinului

            if(paths[neighbor] > paths[nod] + cost_neighbor){

                if(paths[neighbor] != 200000200){

                    tree.erase(tree.find(make_pair(paths[neighbor], neighbor)));
                }

                paths[neighbor] = paths[nod] + cost_neighbor;

                //adaugam in arbore perechea data de vecin si costul drumului pana la acesta

                tree.insert(make_pair(paths[neighbor], neighbor));
            }
        }
    }

    //pentru nodurile pentru care distanta de la nodul sursa la ele a ramas infinit, inseamna ca nu exista drum de la nodul sursa la acetea;
    //asadar, trebuie sa modificam in vectorul cu distante minim aceste valori cu 0;

    for(int i = 1; i <= this->m_number_of_nodes; i++){

        if(paths[i] == 200000200) paths[i] = 0;
    }

    return paths;
}

vector< vector<int> > Oriented_graph_with_costs::bellman_ford(vector<vector<int>> costs_matrix) {

    vector<vector<int>> path_matrix;
    vector<int> aux;

    //initializam matricea de drumuri cu numarul de noduri ale grafului nostru

    aux.assign(this->m_number_of_nodes + 1, 0);
    path_matrix.assign(this->m_number_of_nodes + 1, aux);

    //initial, pe fiecare pozitie (i, j) in matricea de drumuri se afla costul de a ajunge de la i la j prin muchia directa;

    for(int i = 1; i <= this->m_number_of_nodes; i++){

        for(int j = 1; j <= this->m_number_of_nodes; j++){

            path_matrix[i][j] = this->m_costs_matrix[i][j];
        }
    }

    for(int k = 1; k <= this->m_number_of_nodes; k++){

        for(int i = 1; i <= this->m_number_of_nodes; i++){

            for(int j = 1; j <= this->m_number_of_nodes; j++){

                if(i != j && path_matrix[i][k] != 0 && path_matrix[k][j] != 0){

                    if(path_matrix[i][j] > path_matrix[i][k] + path_matrix[k][j]){

                        path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];

                    }else if (path_matrix[i][j] == 0){

                        path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
                    }
                }
            }
        }
    }

    return path_matrix;
}

int Oriented_graph_with_costs::hamilton() {

    vector< vector<int> > minimum_costs;
    vector<int> aux;

    //initializam matricea cu costuri minime ale drumurilor de la un nod la altul -> avem atatea linii
    // cate variante de drumuri putem avea, adica atatea linii cate numere in baza 2 cu nr_noduri cifre putem scrie.
    // avem atatea coloane cate noduri sunt

    aux.assign(m_number_of_nodes + 1, 100000000);
    minimum_costs.assign(1 << m_number_of_nodes, aux);

    //initializam lantul format dintr-un singur nod cu cost 0
    minimum_costs[1][0] = 0;

    //formam matricea costurilor minime posibile ale tuturor drumurilor posibile - parcurgem toate drumurile posibile si,
    //pentru fiecare nod, verificam daca acel nod se afla in drumul curent sau nu, caz in care trebuie sa actualizam costul minim al lantului
    //care ajunge in acel nod

    for(int i = 0; i < 1 << m_number_of_nodes; i++){

        for(int j = 0; j < m_number_of_nodes; j++){

            //pentru fiecare drum, parcurgem toate nodurile grafului si, pentru nodurile care fac parte din drum, incercam sa actualizam costurile minime ale drumurilor pana la j prin i

            //i este drumul; j este nodul; daca j face parte din i, atunci bitul de pe pozitia j din i este 1
            if( i & (1 << j) ){

                //daca nodul j face parte din drumul curent i, parcurgem vecinii nodului j si, daca vecinul face parte si el din drum, atunci incercam sa actualizam costul minim al drumului
                //pana la nodul j prin drumul i

                for(int k = 0; k < m_neighbors[j].size(); k++){

                    if( i & (1 << m_neighbors[j][k]) ){

                        //daca vecinul nodului apartine drumului, verificam daca e cazul sa actualizam minimul costurilor drumurilor pana la nodul j prin drumul i
                        //cu suma dintre costul minim pana la vecin + costul muchiei de la vecin la j

                        minimum_costs[i][j] = min( minimum_costs[i][j], minimum_costs[i ^ (1 << j) ][ m_neighbors[j][k] ] + m_costs_matrix[ m_neighbors[j][k] ][j]);
                    }
                }
            }
        }
    }

    //aflam costul minim al unnui ciclu
    int mini = 100000000;

    for(int i = 0; i < m_neighbors[0].size(); i++){
        mini = min(mini, minimum_costs[ (1 << m_number_of_nodes) - 1 ][ m_neighbors[0][i] ] + m_costs_matrix[ m_neighbors[0][i] ][0]);
    }

    //daca mini a ramas infinit, inseamna ca graful nu este hamiltonian

    if(mini == 100000000) return -1;

    return mini;
}

//CLASA ARBORE
class Tree:Graph{
private:
    vector< vector<int> > m_adjacency_list;
    vector<int> m_fathers_array;
    vector<int> m_ranks_array;
public:
    //citirea arborelui
    void read_graph(char *file);

    //BFS pentru diametrul arborelui
    void BFS(int node, int& diameter, int& last);

    //initializarea vectorului de tati
    void initialize_fathers_array();

    //initializarea vectorului de ranguri
    void initialize_ranks_array(int value);

    //setarea numarului de noduri
    void set_number_of_nodes(int number_of_nodes);

    //gasirea unui nod intr-un arbore -> returneaza numarul multimii in care se afla (identificat prin nodul radacina al arborelui ce reprezinta multimea)
    int find(int node);

    //reuninea a 2 multimi in arbore -> primeste ca argument numerele multimilor ce trebuie reunite (adica nodurile radacina ale celor 2 arbori ce reprezinta multimile)
    void unify(int set1, int set2);
};

//METODE PUBLICE ARBORE

void Tree::read_graph(char *file) {

    ifstream f(file);
    vector<int> aux;

    //citim numarul de noduri si initializam lista de vecini cu cu numarul de noduri dat

    f >> this->m_number_of_nodes;

    this->m_adjacency_list.assign(this->m_number_of_nodes + 1, aux);

    //citim muchiile arborelui si marcam pentru fiecare node vecinul sau in matricea de vecini

    for(int i = 0; i < this->m_number_of_nodes; i++){
        int x, y;
        f >> x >> y;

        this->m_adjacency_list[x].push_back(y);
        this->m_adjacency_list[y].push_back(x);
    }
}

void Tree::BFS(int node, int &diameter, int &last) {
    //initializam vectorul de distances minime

    vector<int> distances;
    distances.assign(this->m_number_of_nodes + 1, 0);

    int current_node;
    //in nodes_queue vom pune nodurile pe massura ce le parcurgem
    queue<int> nodes_queue;

    //initial toate nodurile sunt nevizitate, asaa ca initializam visited[orice node] = 0
    vector<int> visited;
    visited.assign(this->m_number_of_nodes + 1, 0);

    //adaugam nodul sursa in nodes_queue si il marcam ca si vizitat
    nodes_queue.push(node);
    visited[node] = 1;

    //actualizam vectorul de distances pentru nodul current_node cu distanta pana la el, adica 1
    distances[node] = distances[node] + 1;

    //facem BFS-ul
    while(!nodes_queue.empty()){

        current_node = nodes_queue.front();

        //parcurgem vecinii nodului current_node si pe fiecare vecin nevizitat il adaugam in nodes_queue, ii actualizam distanta pana la el si il marcam ca si vizitat

        for(int i=0; i < this->m_adjacency_list[current_node].size(); i++){

            if(visited[this->m_adjacency_list[current_node][i]] == 0){
                nodes_queue.push(this->m_adjacency_list[current_node][i]);

                distances[nodes_queue.back()] = distances[current_node] + 1;

                visited[this->m_adjacency_list[current_node][i]] = 1;

                diameter = distances[this->m_adjacency_list[current_node][i]];
                last = this->m_adjacency_list[current_node][i];
            }
        }

        //am terminat cu nodul current_node, il scoatem din nodes_queue
        nodes_queue.pop();
    }
}

void Tree::initialize_fathers_array() {

    if(m_fathers_array.size() <= m_number_of_nodes) m_fathers_array.resize(m_number_of_nodes + 1);

    for(int i = 1; i <= m_number_of_nodes; i++){
        m_fathers_array[i] = i;
    }
}

void Tree::initialize_ranks_array(int value) {

    m_ranks_array.assign(m_number_of_nodes + 1, value);
}

void Tree::set_number_of_nodes(int number_of_nodes) {

    m_number_of_nodes = number_of_nodes;
    m_fathers_array.resize(m_number_of_nodes + 1);
    m_ranks_array.resize(m_number_of_nodes + 1);
}

//gasirea multimii din care face parte un element: O(log n), unde n este numarul de noduri ale arborelui

int Tree::find(int node) {
    int root;

    //gasesc radacina arborelui din care face parte nodul dat <=> pornesc din nodul dat si urc in arbore pana gasesc nodul care pointeaza catre el insusi

    root = node;

    while(m_fathers_array[root] != root){

        root = m_fathers_array[root];
    }

    //facem compresia durmurilor, pentru a scadea timpul de executie

    //acum ca stim unde se afla nodul x, urcam din tata in tata pana la radacina si il legam pe fiecare nod prin care trecem de radacina
    //astfel, cand vom avea urmatoarea interogare, avem nodul cautat direct legat de radacina, asa ca vom putea raspunde in O(1)

    do{
        int aux;

        aux = m_fathers_array[node];
        m_fathers_array[node] = root;
        node = aux;

    }while(m_fathers_array[node] != node);

    return root;
}

//reunirea a 2 multimi: O(1)

void Tree::unify(int set1, int set2) {

    //multimea cu rang mai mic va deveni surbaroe al celei cu rang mai mare <=> tatal radacinii multimii cu rangul mai mic devine radacina celei cu rangul mai mare

    if(m_ranks_array[set1] > m_ranks_array[set2]) m_fathers_array[set2] = set1;
    else m_fathers_array[set1] = set2;

    //daca ambele multimi au acelasi rang, inseamna ca multime-mama a devenit a doua, deci ii cresc rangul

    if(m_ranks_array[set1] == m_ranks_array[set2]) m_ranks_array[set2]++;
}

//CLASA RETELE DE TRANSPORT

class Flow_network: Directed_graph{
private:
    vector< vector<int> > m_capacities_matrix;

public:
    //citirea fluxului de transport
    void read_graph(char *file);

    //metoda edmonds_karp -> returneaza fluxul maxim care poate fi transportat
    int edmonds_karp();

private:
    int BFS(vector<int>& father, vector< vector<int> >& f, vector<int>& visited);
};

//METODE PUBLICE RETEA DE TRANSPORT

void Flow_network::read_graph(char *file) {
    ifstream f(file);
    vector<int> aux;
    int number_of_edges;

    //citim numarul de noduri si numarul de muchii si initializam lista de vecini si matricea de capacitati

    f >> m_number_of_nodes >> number_of_edges;

    m_adjancency_list.assign(m_number_of_nodes + 1, aux);
    aux.assign(m_number_of_nodes + 1, 0);
    m_capacities_matrix.assign(m_number_of_nodes + 1, aux);

    //parcurgem muchiile si, la fiecare, adaugam vecinii fiecarui nod in listele de vecini si actualizam capacitatea de pe pozitia corespunzatoare muchiei in matricea de capacitati
    for(int i = 0; i < number_of_edges; i++){
        int x, y, capacity;

        f >> x >> y >> capacity;

        m_capacities_matrix[x][y] = m_capacities_matrix[x][y] + capacity;

        m_adjancency_list[x].push_back(y);
        m_adjancency_list[y].push_back(x);
    }

}

int Flow_network::edmonds_karp() {

    //initializam flow-ul maxim cu 0
    int flow = 0;

    vector<int> father;
    vector< vector<int> > f;
    vector<int> visited;

    //initializam vectorul de tati pentru fiecare nod cu 0

    father.assign(m_number_of_nodes + 1, 0);

    //initializam vectorul de fluxuri pentru fiecare nod cu un vector gol

    f.assign(m_number_of_nodes + 1, vector<int>());

    //cat timp nu am atins ultimul nod

    while(BFS(father,f,visited)){

        //parcurgem vecinii ultimului nod

        for(int i = 0; i < m_adjancency_list[m_number_of_nodes].size(); i++){
            int node;

            node = m_adjancency_list[m_number_of_nodes][i];

            //pentru fiecare vecin, verificam daca fluxul de la vecinul ultimului nod la ultimul nod din matricea de fluxuri este diferit
            //de capacitatea de a ajunge de la vecin la ultimul nod din matricea de capacitati; daca cele 2 sunt diferite si vecinul nu a fost inca vizitat
            //inseamna ca putem conecta vecinul la flux

            if(f[node][m_number_of_nodes] != m_capacities_matrix[node][m_number_of_nodes] && visited[node] != 0) {

                //conectam vecinul la flux

                father[m_number_of_nodes] = node;

                int fmin = 1000000;

                //urcam pe arbore din tata in tata si cautam diferenta minima intre capacitatea si fluxul de la tata nodului la nod(care este vecinul pe care il adaugam la flux)

                for (node = m_number_of_nodes; node != 1; node = father[node]) {
                    fmin = min(fmin, m_capacities_matrix[father[node]][node] - f[father[node]][node]);
                }

                //daca exista o diferenta intre capacitate si flux, atunci actualizam fluxul din tata in tata in tatal vecinului

                if (fmin != 0) {

                    for (node = m_number_of_nodes; node != 1; node = father[node]) {

                        f[father[node]][node] = f[father[node]][node] + fmin;
                        f[node][father[node]] = f[node][father[node]] - fmin;
                    }

                    //actualizam rezultatul fluxului final cu fluxul pe care l-am adaugat

                    flow = flow + fmin;
                }
            }
        }
    }
    return flow;
}

//METODE PRIVATE RETEA DE TRANSPORT

//BFS-ul pe care il folosim la edmonds_karp() la aflarea fluxului maxim

int Flow_network::BFS(vector<int>& father, vector< vector<int> >& f, vector<int>& visited) {
    vector<int> cd;

    //initializam vectorul cd pentru maxim 1024 de noduri (el este coada tipica din BFS)
    cd.assign(1024,0);

    //in cd[0] vom retine numarul nodurilor din vectorul cd; initial avem doar nodul 1
    cd[0] = cd[1] = 1;

    //initializam vectorul de noduri vizitate
    visited.assign(m_number_of_nodes + 1, 0);

    //marcam primul nod ca vizitat
    visited[1] = 1;

    //parcurgem nodurile din cd

    for(int i = 1; i <= cd[0]; i++){
        int node;

        node = cd[i];

        //daca nodul nostru nu este ultimul nod, atunci ii parcurgem vecinii si incercam sa gasim un vecin nevizitat la care fluxul difera de capacitate

        if(node != m_number_of_nodes) {

            for (int j = 0; j < m_adjancency_list[node].size(); j++) {
                int neighbor;

                neighbor = m_adjancency_list[node][j];

                //daca vecinul nostru este nevizitat si fluxul de la nodul nostru din cd la vecin este diferit de capacitatea de la nodul nostru la vecin,
                //atunci il marcam ca si vizitat, il adaugam in cd si facem optimizare in arbore: marcam tatal vecinului direct nodul nostru

                if (m_capacities_matrix[node][neighbor] != f[node][neighbor] && visited[neighbor] == 0) {

                    visited[neighbor] = 1;

                    cd[++cd[0]] = neighbor;

                    father[neighbor] = node;
                }
            }
        }
    }

    //returnam daca prin BFS s-a ajuns la ultimul nod sau nu

    return visited[m_number_of_nodes];
}

//CLASA MULTIGRAF

class Multigraph:Graph{
private:
    vector< vector<int> > m_nodes_edges;
    vector< pair<int,int> > m_edges;
public:
    //citirea multigrafului

    void read_graph(char *file);

    //euler(nod) -> determina un ciclu eulerian din multigraf si il returneaza, sau returneaza -1 daca graful nu are niciun ciclu eulerian
    vector<int> euler(int nod);

private:
    bool check_even_degrees();
};

//METODE PUBLICE MULTIGRAF

void Multigraph::read_graph(char *file) {
    ifstream f(file);

    int number_of_edges;

    vector<int> aux;

    //citim numarul de noduri si numarul de muchii

    f >> m_number_of_nodes >> number_of_edges;

    //initializam matricea de muchii si vectorii cu nodurile sursa si nodurile destinatie ale muchiilor

    m_nodes_edges.assign(m_number_of_nodes + 1, aux);
    m_edges.resize(number_of_edges + 1);

    for(int i = 0; i < number_of_edges; i++){

        //citim fiecare muchie in parte

        int x,y;
        f >> x >> y;

        //actualizam matricea de muchii: la x si la y marcam existenta muchiei i

        m_nodes_edges[x].push_back(i);
        m_nodes_edges[y].push_back(i);

        //marcam cum exact este aceasta muchie: de la x la y, deci actualizam vectorul de noduri de sursa ( adaugand x)
        // si cel de noduri destinatie (adaugand y)

        m_edges[i] = make_pair(x,y);
    }

}

vector<int> Multigraph::euler(int nod) {

    vector<int> euler_cycle;

    //una din conditiile ca un graf sa fie eulerian este sa aiba toate nodurile cu graduri pare, asa ca testam acest lucru

    if(!this->check_even_degrees()){

        euler_cycle.push_back(-1);
        return euler_cycle;
    }

    stack<int> nodes;
    vector<int> visited_edges;

    //initializam vectorul de muchii vizitate: initial toate sunt nevizitate

    visited_edges.assign(m_edges.size(), 0);

    //adaugam in stiva cu ciclul format momentan primul nod: cel dat

    nodes.push(nod);

    //cat timp stiva nu e goala <=> cat timp mai avem noduri in ciclul format

    while(!nodes.empty()){

        //preluam nodul curent din ciclul format

        int current_node;

        current_node = nodes.top();

        //daca nodul curent are vecini, luam muchia catre un vecin aleator al nodul curent - aici ultimul, pentru a-l putea elimina usor

        if(m_nodes_edges[current_node].size() != 0){

            int random_edge;

            random_edge = m_nodes_edges[current_node].back();

            //eliminam muchia aleasa

            m_nodes_edges[current_node].pop_back();

            //daca muchia nu a mai fost vizitata pana acum, atunci luam muchia care pleaca din el si adaugam nodul destinatie in stiva cu ciclul format

            if(visited_edges[random_edge] == 0){

                //marcam muchia ca vizitata

                visited_edges[random_edge] = 1;

                //adaugam vecinul la care ne trimite muchia in stiva cu ciclul eulerian curent

                nodes.push(m_edges[random_edge].first ^ m_edges[random_edge].second ^ current_node);
            }
        } else {
            //daca nodul curent nu are vecini, il scoatem din stiva cu ciclul eulerian format si il adaugam in rezultat

            nodes.pop();
            euler_cycle.push_back(current_node);
        }
    }

    return euler_cycle;
}

//METODE PRIVATE MULTIGRAF

//check_even_degrees -> verifica daca toate nodurile muligrafului au grad par

bool Multigraph::check_even_degrees() {

    for(int i = 1; i <= m_number_of_nodes; i++){
        if(m_nodes_edges[i].size() % 2 == 1){
            return false;
        }
    }

    return true;

}

//HELPERE
void print_vector(vector<int> v, char *file, int i = 0){
    ofstream g(file);
    vector<int>::iterator it;

    for(it = v.begin() + 1 + i; it != v.end(); it++){
        g << *it <<" ";
    }
}

void print_vector_of_unordered_sets(vector< unordered_set<int> > v, char *file, int i = 0){
    ofstream g(file);
    vector< unordered_set<int> >::iterator it;
    unordered_set<int>::iterator it_u;

    g << v.size() << "\n";

    for(it = v.begin() + i; it != v.end(); it++){

        for(it_u = it->begin(); it_u != it->end(); it_u++){
            g << *it_u << " ";
        }
        g << "\n";
    }
}

void print_vector_of_vectors(vector< vector<int> >v, char *file, int i = 0, bool show_size = true){
    ofstream g(file);
    vector< vector<int> >::iterator it;
    vector<int>::iterator it_u;

    if(show_size == true) g << v.size() << "\n";

    for(it = v.begin() + i; it != v.end(); it++){

        for(it_u = it->begin() + i; it_u != it->end(); it_u++){
            g << *it_u << " ";
        }
        g << "\n";
    }
}

void print_stack(stack<int> s, char *file){
    ofstream g(file);

    while(!s.empty()){

        g << s.top() << " ";
        s.pop();
    }
}

void read_vector(vector<int>& v, char *file){
    ifstream f(file);
    int size;

    f >> size;

    for(int i = 0; i < size; i++){
        int value;

        f >> value;

        v.push_back(value);
    }
}

int main() {
            //BFS INFOARENA

    /*Directed_graph g;
    int source;
    vector<int> distances;

    //citim graful si nodul sursa din care trebuie sa formam drumurile minime catre fiecare nod

    source = g.read_graph_with_starting_node("../bfs.in");

    //apelam BFS, care ne va intoarce un vector in care pe pozitia i se afla numarul minim de arce ce trebuie parcurse
    //pentru a ajunge de la nodul sursa dat ca argument la nodul i

    distances = g.BFS(source);

    //afisam vectorul de distante(functia afiseaza de la pozitia 1 incolo, deci e ok)

    print_vector(distances, "../bfs.out");*/

            //DFS INFOARENA
    /*Undirected_graph g;
    ofstream out("../dfs.out");
    int number;

    //citim graful neorientat dat

    g.read_graph("../dfs.in");

    //metoda number_of_connected_components() ne va returna un int cu numarul de componente conexe

    number = g.number_of_connected_components();

    out << number;*/

            //COMPONENTE BICONEXE INFOARENA

    /*Undirected_graph g;
    vector< unordered_set<int> > biconnected_components;

    //citim graful neorientat dat

    g.read_graph("../biconex.in");

    //metoda generate_biconnected_components() un vector in care pe fiecare pozitie se afla cate un set ce contine o componenta biconexa

    biconnected_components = g.generate_biconnected_components();

    //afisam vectorul de componente obtinut

    print_vector_of_unordered_sets(biconnected_components, "../biconex.out");*/

            //CTC INFOARENA
    /*Directed_graph g;
    vector< vector<int> > strongly_connected_components;

    //citim graful orientat fara costuri dat

    g.read_graph("../ctc.in");

    //metoda create_strongly_connected_components() ne returneaza un vector in care pe fiecare pozitie este cate un vector ce contine o componenta tare conexa

    strongly_connected_components = g.create_strongly_connected_components();

    //afisam vectorul de vectori cu componente tare conexe obtinut

    print_vector_of_vectors(strongly_connected_components, "../ctc.out");*/

            //SORTARE TOPOLOGICA INFOARENA

    /*Directed_graph g;
    stack<int> topological_sort;

    //citim graful orientat fara costuri dat

    g.read_graph("../sortaret.in");

    //metoda topological_sort() ne returneaza o stiva in care sunt asezate nodurile in ordinea data de sortarea topologica

    topological_sort = g.topological_sort();

    //afisam vectorul de noduri obtinut

    print_stack(topological_sort, "../sortaret.out");*/

            //HAVEL HAKIMI

    /*Graph g;
    vector<int> v;
    ofstream out("../hakimi.out");

    //citim secventa din care incercam sa construim un graf

    read_vector(v,"../hakimi.in");

    //metoda hakimi(vector) ne returneaza true daca putem construi un graf din vectorul dat astfel incat fiecare nod i sa aiba gradul vector[i], respectiv false
    //daca nu se poate

    if(g.hakimi(v) == true)  out << "Posibil";
    else out << "Imposibil";*/

            //MUCHII CRITICE GRAF NEORIENTAT LEETCODE

    /*Undirected_graph g;
    vector< vector<int> > critical_edges;

    //citim graful neorientat dat

    g.read_graph("../critice.in");

    //metoda find_critical_edges() ne returneaza un vector in care pe fiecare pozitie se afla un vector de muchii critice

    critical_edges = g.find_critical_edges();

    //afisam vectorul de vectori obtinut

    print_vector_of_vectors(critical_edges, "../critice.out");*/

            //APM INFOARENA - ALGORITMUL LUI PRIM
    /*Unoriented_graph_with_costs g;
    vector< pair<int,int> > apm;
    ofstream out("../apm.out");
    int cost_APM = 0;

    //citim graful neorientat cu costuri dat

    g.read_graph("../apm.in");

    //metoda prim() foloseste algoritmul lui Prim pentru a-mi returna un vector in care pe fiecare pozitie se afla perechea (x,y) cu semnificatia ca arborele
    //partial de cost minim contine muchie de la nodul x la nodul y; in parametrul transmis prin referinta obtinem costul arborelui

    apm = g.prim(cost_APM);

    //afisam costul APM-ului si numarul de muchii

    out << cost_APM << "\n";

    out << apm.size() << "\n";

    //afisam fiecare muchie a apm-ului

    for(int i = 0; i < apm.size(); i++){
        out << apm[i].first << " " << apm[i].second << "\n";
    }*/

            //PADURI DE MULTIMI DISJUNCTE INFOARENA

    //Cele 2 multimi vor fi reprezentate ca 1 arbore
    /*ifstream in("../disjoint.in");
    ofstream g("../disjoint.out");
    int nodes, number_of_tasks;
    Tree set;

    //citim numarul de multimi
    in >> nodes;

    //numarul de multimi <=> numarul de noduri ale arborelui (initial fiecare multime are doar elementul i), asa ca setam ca arborele cu numar de noduri = numar de multimi

    set.set_number_of_nodes(nodes);

    //initial, tatal fiecarui nod este chiar el (pentru ca fiecare multime i contine doar elementul i) si rangul fiecarui arbore este 1
    set.initialize_fathers_array();
    set.initialize_ranks_array(1);

    //citim numarul de operatii
    in >> number_of_tasks;

    //citim fiecare operatie
    for(int i = 0; i < number_of_tasks; i++){

        int task, x, y;
        in >> task >> x >> y;

        if(task == 2){
            //daca task-ul este 2, atunci trebuie sa verificam daca x si y se afla in aceeasi multime; afisam DA / NU, dupa caz

            if( set.find(x) == set.find(y) ) g << "DA\n";
            else g << "NU\n";

        }else{
            //daca task-ul este 1, atunci trebuie sa reunim multimea in care se afla elementul x cu cea in care se afla elementul y;
            int index_x, index_y;

            index_x = set.find(x);
            index_y = set.find(y);

            set.unify(index_x, index_y);

        }
    }*/

            //DIJKSTRA INFOARENA
    /*Oriented_graph_with_costs g;
    vector<int> minimum_distances;

    //citim graful orientat cu costuri dat

    g.read_graph("../dijkstra.in");

    //metoda dijkstra(nod) imi returneaza un vector in care pe fiecare pozitie i se afla distanta minima de la nodul dat ca argument la nodul i

    minimum_distances = g.dijkstra(1);

    //afisam vectorul rezultat

    print_vector(minimum_distances, "../dijkstra.out", 1);*/

            //BELLMAN FORD
    /*Oriented_graph_with_costs g;
    vector< vector<int> > paths;

    //citim garful orientat cu costuri dat

    g.read_costs_matrix("../royfloyd.in");

    //metoda bellman_ford(vectori de vectori de int-uri) primeste ca argument matricea de costuri si returneaza matricea de drumuri

    paths = g.bellman_ford(g.get_costs_matrix());

    //afisam matricea de drumuri obtinuta, cu argumentul false pentru ca acest helper afiseaza si numarul de linii ale matricei daca nu dam acest argument

    print_vector_of_vectors(paths,"../royfloyd.out",1,false);*/

            //FLUXUL MAXIM INFOARENA

    /*Flow_network in;
    ofstream g("../maxflow.out");
    int maxflow;

    //citim reteaua de transport data

    in.read_graph("../maxflow.in");

    //algoritmul edmonds_karp() ne returneaza un int cu fluxul maxim

    maxflow = in.edmonds_karp();

    g << maxflow;*/

            //DIAMETRUL UNUI ARBORE
    /*ofstream g("../darb.out");
    Tree t;
    t.read_graph("../darb.in");


    int diameter = 0, last = 0;

    //parcurgem arborele prin BFS

    t.BFS(1, diameter, last);
    t.BFS(last,diameter,last);

    g << diameter;*/

            //CICLUL EULERIAN INFOARENA
    /*Multigraph g;
    vector<int> euler_cycle;

    //citesc multigraful dat

    g.read_graph("../ciclueuler.in");

    //metoa euler(nod) imi returneaza un vector cu un ciclu euler pornind din nodul dat sau un vector format doar din valoarea -1 daca graful nu este eulerian

    euler_cycle = g.euler(1);

    //dam ca argument la printarea vectorului -1 pentru ca printarea sa inceapa de pe pozitia 0

    print_vector(euler_cycle, "../ciclueuler.out", -1);*/

            //CICLUL HAMILTONIAN DE COST MINIM INFOARENA

    /*ofstream out("../hamilton.out");

    Oriented_graph_with_costs g;
    int hamilton;

    //citim graful orientat cu costuri dat

    g.read_graph_with_costs_matrix("../hamilton.in");

    //metoda hamilton() imi returneaza un int cu costul ciclului hamiltonian minim, sau -1 daca graful nu este eulerian

    hamilton = g.hamilton();

    if(hamilton == -1) out << "Nu exista solutie";
    else out << hamilton;*/

            //CUPLAJ MAXIM IN GRAF BIPARTIT INFOARENA

    Unoriented_bipartite_graph g;
    vector< pair<int,int> > maximum_matching;
    ofstream out("../cuplaj.out");

    //citim graful
    g.read_graph("../cuplaj.in");

    //obtinem in vectorul de perechi cuplajul maxim
    maximum_matching = g.hopcroft_karp();

    //afisam marimea cuplajului si cuplajul
    out << maximum_matching.size() << "\n";

    for(int i = 0; i < maximum_matching.size(); i++){

        out << maximum_matching[i].first << " " << maximum_matching[i].second << "\n";
    }

    return 0;
}