#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

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;
}

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 UNORIENTED GRAPH

class Unoriented_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 Unoriented_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

    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);
    }
}

void Unoriented_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);
        }
    }
}

int Unoriented_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 node 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;
}

vector< unordered_set<int> >Unoriented_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 si nivelul cel mai de sus pentru fiecare node

    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);

    return biconnected_components;
}

vector< vector<int> > Unoriented_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;

    visited.assign(m_number_of_nodes + 1, 0);
    prec.resize(m_number_of_nodes + 1);
    low_link_values.resize(m_number_of_nodes + 1);
    arrival_times.assign(m_number_of_nodes + 1, -1);

    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
void Unoriented_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;

                    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

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

void Unoriented_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_graph_coupler:Unoriented_graph{
private:
    int m_number_of_left_nodes;

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

    //returnarea cuplajului maxim
    vector< pair<int, int> > hopcroft_karp();

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

//METODE GRAF NEORIENTAT BIPARTIT

void Unoriented_graph_coupler::read_graph(char *file) {
    ifstream f(file);
    int left, right, number_of_edges;
    vector<int> aux;

    //citim numarul din multimea de stanga si cea de dreapta (numarul de noduri va fi suma) si numarul de muchii

    f >> left >> right >> number_of_edges;

    m_number_of_left_nodes = left;
    m_number_of_nodes = left + right;

    //initializam matricea de adiacenta pentru numarul nodurilor din stanga
    m_adjancency_list.assign(left + 1, aux);

    //citim fiecare muchie si o adaugam in matricea de adiacenta (doar intr-un sens deoarece matricea cuprinde doar nodurile din stanga)
    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_graph_coupler::hopcroft_karp() {

    vector< pair<int, int> > maximum_coupler;
    vector<int> left_pair, right_pair;
    vector<int> visited;
    bool enough = false;

    //initializam perechile din dreapta ale nodurilor din stanga cu 0 si perechile din stanga a nodurilor din sreapta tot cu 0

    right_pair.assign(m_number_of_left_nodes + 1, 0);
    left_pair.assign(m_number_of_nodes - m_number_of_left_nodes + 2, 0);

    //cat timp mai pot adauga lanturi noi care sa plece dintr-un node din stanga si sa ajunga tot intr-un din stanga (ambele fara pereche)
    //incerc sa formez varianta maximala, fara alte lanturi de adaugat

    while(enough == false){

        //initializam vectorul de noduri vizitate, dar doar pentru nodurile din stanga
        visited.assign(m_number_of_left_nodes + 1, 0);

        //presupun ca aceasta este varianta de lant maxima
        enough = true;

        //iau toate nodurile din stanga
        for(int i = 1; i <= m_number_of_left_nodes; i++){

            if(right_pair[i] == 0 && DFSCoupler(i, visited, left_pair, right_pair) == true){

                enough = false;
            }
        }
    }

    //formam cuplajul: luam toate nodurile din stanga care au legatura in dreapta
    for(int i = 1; i <= m_number_of_left_nodes; i++){

        if(right_pair[i] != 0){

            maximum_coupler.push_back(make_pair(i, right_pair[i]));
        }
    }

    return maximum_coupler;
}

//METODE PRIVATE GRAF NEORIENTAT BIPARTIT

bool Unoriented_graph_coupler::DFSCoupler(int node, vector<int>& visited, vector<int>& left_pair, vector<int>& right_pair) {

    //daca nodul a fost deja vizitat, returnam false
    if(visited[node] != 0){
        return false;
    }

    //marcam nodul ca vizitat
    visited[node] = 1;

    //parcurgem vecinii nodului dat si incercam sa formam lant
    for(int i = 0; i < m_adjancency_list[node].size(); i++){
        int neighbor;

        neighbor = m_adjancency_list[node][i];

        if(left_pair[neighbor] == 0 || DFSCoupler(neighbor, visited, left_pair, right_pair) == true){

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

            return true;
        }
    }

    return false;
}

//CLASA ORIENTED GRAPH

class Oriented_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 Oriented_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 Oriented_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 -> returneaza un vector in care pe pozitia i se afla numarul minim de arce ce trebuie parcurse de la sursa data pana la nodul i

vector<int> Oriented_graph::BFS(int source) {
    //initializam vectorul de distances minime

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

    int curent;

    //in coada vom pune nodurile pe massura ce le parcurgem
    queue<int> current_nodes;

    //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 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
    while( !current_nodes.empty() ){

        curent = current_nodes.front();

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

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

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

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

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

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

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

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

        distances[i]--;
    }

    return distances;
}

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

    vector<vector<int>> strongly_connected_components;

    stack<int> current_component;
    int current_arrival_time = 0;

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

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

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

    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;
}

void Oriented_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);
    }
}

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

    visited.assign(m_number_of_nodes + 1, 0);

    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

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

    visited[node] = 1;

    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);
        }
    }
    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));
    }

}

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);
    }

    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

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;
    }
}

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);
}

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;
    }
}

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;
}

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 nodu; 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;
public:
    //citirea arborelui
    void read_graph(char *file);

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

//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();
    }
}

//CLASA RETELE DE TRANSPORT

class Flow_network:Oriented_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;

    //initializam vectorul de tati si matricea cu fluxuri
    vector<int> father;
    vector< vector<int> > f;
    vector<int> visited;

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

    while(BFS(father,f,visited)){
        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];

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

                father[m_number_of_nodes] = node;

                int fmin = 1000000;

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

                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;
                    }

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

//METODE PRIVATE RETEA DE TRANSPORT

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
    cd.assign(1024,0);

    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;

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

        node = cd[i];

        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];

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

                    visited[neighbor] = 1;

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

                    father[neighbor] = node;
                }
            }
        }
    }

    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

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

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

    distances = g.BFS(source);

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

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

    g.read_graph("../dfs.in");
    number = g.number_of_connected_components();

    out << number;*/

            //COMPONENTE BICONEXE INFOARENA

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

    g.read_graph("../biconex.in");
    biconnected_components = g.generate_biconnected_components();

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

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

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

    strongly_connected_components = g.create_strongly_connected_components();

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

            //SORTARE TOPOLOGICA INFOARENA

    /*Oriented_graph g;
    stack<int> topological_sort;

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

    topological_sort = g.topological_sort();

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

            //HAVEL HAKIMI

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

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

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

            //MUCHII CRITICE GRAF NEORIENTAT LEETCODE

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

    g.read_graph("../critice.in");
    critical_edges = g.find_critical_edges();

    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;

    g.read_graph("../apm.in");
    apm = g.prim(cost_APM);

    out << cost_APM << "\n";

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

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

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

    g.read_graph("../dijkstra.in");
    minimum_distances = g.dijkstra(1);

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

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

    g.read_costs_matrix("../royfloyd.in");
    paths = g.bellman_ford(g.get_costs_matrix());

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

            //FLUXUL MAXIM INFOARENA

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

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

    maxflow = f.edmonds_karp();

    out << maxflow;*/

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


    int diameter = 0, last = 0;

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

    out << diameter;*/

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

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

    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;

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

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

            //CUPLAJ MAXIM IN GRAF BIPARTIT INFOARENA

    /*Unoriented_graph_coupler g;
    ofstream out("../cuplaj.out");
    g.read_graph("../cuplaj.in");

    vector< pair<int, int> > maximum_coupler;

    maximum_coupler = g.hopcroft_karp();

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

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