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

using namespace std;

class Graph{
private:
                    //DATE MEMBRE

    int graph_Nodes;                                        //numar de noduri

    vector<vector<int>> graph_adjacency_list;               //lista de adiacenta
    vector<vector<pair<int,int>>> graph_adjacency_list_with_costs;    //lista de adiacenta pentru graf cu costuri

                    //METODE UTILE

    int read_BFS_Infoarena(char *file);     //citeste un graf orientat fara costuri si nodul sursa de la care se calculeaza distantele in BFS pe infoarena

    vector<int> create_Minimum_Paths(int node);    //returneaza vectorul cu distante pentru problema BFS de pe infoarena

    vector<int> initViz();  //marcheaza toate nodurile ca nevizitate

    void print_Minimum_Paths(char *file, vector<int> distances);   //afiseaza caile minime calculate in BFS infoarena

    int count_Connected_Components();       //returneaza numarul componentelor conexe

    vector<unordered_set<int>> create_Biconnected_Components(); //returneaza vectorul de componente biconexe

    void DFSBiconnected(int nodCurent, int precedent, int pas, vector<int>& vizPasi, vector<int>& low_link_values,vector<unordered_set<int>>& biconnected_components,stack<pair <int, int>>& StivaMuchiiComponentaBiconexaCurenta); //DFS pentru aflarea numarului de componente biconexe

    vector<vector<int>> Create_Strongly_Connected_Components(); //genereaza vectorul de componente tare conexe

    void tarjan(int nod,stack<int>& StivaComponentaTareConexaCurenta,vector<int>& isInStiva,vector<int>& arrivalTime, int& arrivalTimeCurent, vector<int>& lowLinkValue, vector<vector<int>>& strongly_connected_components); //algoritmul tarjan pentru CTC

    void DFSSortareTopologica(int nod, vector<int>& viz, stack<int>& sortare);

    bool hakimi(vector<int>& values, int number_of_values);

    vector<vector<int>> Find_Critical_Edges();

    void DFSCriticals(int node, int& arrival_time, vector<vector<int>>& critical_edges, vector<int>& viz, vector<int>& arrival_times, vector<int>& low_link_values, vector<int>& prec);

    vector<pair<int,int>> create_APM(int& cost_APM);

    void introduce_in_APM(int nod, vector<int>& distante, vector<int>& vec);

    void introduce_in_min_heap(int nod, vector<int>& heap, vector<int>& poz, vector<int> distante);

    int extract_root_min_heap(vector<int>& heap,vector<int>& poz, vector<int> distante);

    void pop(int index, vector<int>& heap, vector<int>& poz, vector<int>& distante);

    void push(int index, vector<int>& heap, vector<int>& poz, vector<int>& distante);
public:
    void read_Unoriented_Graph_Without_Costs(char *file);     //primeste calea catre fisierul text si citeste un graf neorientat fara costuri

    void read_Oriented_Graph_Without_Costs(char *file);     //primeste calea catre fisierul text si citeste un graf orientat fara costuri

    void read_Unoriented_Graph_With_Costs(char *file);     //primeste calea catre fisierul text si citeste un graf orientat cu costuri

    void show_Shortest_Paths(char *file_in, char *file_out);     //primeste calea catre fisierul text cu datele si cel in care trebuie afisate rezultatele,
                                                                // si afiseaza cele mai scurte drumuri ce trebuie parcurse pentru a ajunge din nodul sursa la fiecare nod

    void print_Number_Of_Connected_Components(char *file);  //afiseaza numarul de componente conexe

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

    void print_Biconnected_Components(char *file);  //afiseaza componentele biconexe

    void print_Strongly_Connected_Components(char *file);   //afiseaza componentele tare conexe

    void print_Topological_Sort(char *file);    //afiseaza sortarea topologica

    void generateFromSecventa(char *file_in, char *file_out);

    void print_Critical_Edges(char *file);  //afiseaza muchiile critice intr-un fisier dat

    void print_APM(char *file);     //afiseaza APM
};

//METODELE PUBLICE:
                    //CITIREA UNUI GRAF NEORIENTAT FARA COSTURI

void Graph::read_Unoriented_Graph_Without_Costs(char *file){
    ifstream f(file);
    vector<int> aux;
    int nrMuchii;

    f>>this->graph_Nodes;
    this->graph_adjacency_list.assign(this->graph_Nodes + 1, aux);

    f>>nrMuchii;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->graph_adjacency_list[x].push_back(y);
        this->graph_adjacency_list[y].push_back(x);
    }
}

                    //CITIREA UNUI GRAF ORIENTAT FARA COSTURI

void Graph::read_Oriented_Graph_Without_Costs(char *file){
    ifstream f(file);
    vector<int> aux;
    int nrMuchii;

    f>>this->graph_Nodes;
    this->graph_adjacency_list.assign(this->graph_Nodes + 1, aux);

    f>>nrMuchii;

    for(int i = 0; i < nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->graph_adjacency_list[x].push_back(y);
    }
}


                    //CITIREA UNUI GRAF NEORIENTAT CU COSTURI
void Graph::read_Unoriented_Graph_With_Costs(char *file){
    fstream f(file);
    vector<pair<int,int>> aux;
    int nrMuchii;

    f>>this->graph_Nodes;
    this->graph_adjacency_list_with_costs.assign(this->graph_Nodes + 1, aux);

    f>>nrMuchii;

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

        f >> x >> y >> cost;

        this->graph_adjacency_list_with_costs[x].push_back(make_pair(y,cost));
        this->graph_adjacency_list_with_costs[y].push_back(make_pair(x,cost));
    }
}
                    //PROBLEMA BFS INFOARENA - AFISAREA DRUMURILOR DE LUNGIME MINIMA DE LA UN NOD SURSA LA FIECARE NOD DIN GRAF

void Graph::show_Shortest_Paths(char *file_in, char *file_out){

    int startNode; //nodul sursa de la care se calculeaza distantele catre fiecare nod
    vector<int> minPaths;   //vectorul cu distantele minime

    startNode = this->read_BFS_Infoarena(file_in);

    minPaths = this->create_Minimum_Paths(startNode);

    this->print_Minimum_Paths(file_out, minPaths);

}

                //PROBLEMA DFS INFOARENA - AFISAREA NUMARULUI DE COMPONENTE CONEXE

void Graph::print_Number_Of_Connected_Components(char *file){
    ofstream g(file);

    g<<this->count_Connected_Components();
}

void 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->graph_adjacency_list[node].size(); i++){

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

    }
}

void Graph::print_Biconnected_Components(char *file){
    ofstream g(file);
    vector<unordered_set<int>> biconnected_components;

    biconnected_components = this->create_Biconnected_Components();

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

    for(int i=0; i<biconnected_components.size(); i++){
        for(unordered_set<int>::iterator it = biconnected_components[i].begin(); it != biconnected_components[i].end(); it++){
            g<<*it<<" ";
        }

        g<<"\n";
    }
}

void Graph::print_Strongly_Connected_Components(char *file){
    ofstream g(file);
    vector<vector<int>> strongly_connected_components;

    strongly_connected_components = this->Create_Strongly_Connected_Components();

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

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

        for(int j = 0; j < strongly_connected_components[i].size(); j++){
            g << strongly_connected_components[i][j] << " ";
        }

        g<<"\n";
    }
}

void Graph::print_Topological_Sort(char *file){
    ofstream g(file);

    stack<int> sortare;

    vector<int> viz;
    viz = this->initViz();

    for(int i = 1; i <= this->graph_Nodes; i++){
        if(viz[i] == 0){
            DFSSortareTopologica(i, viz, sortare);
        }
    }

    while(sortare.size() != 0){
        g<<sortare.top()<<" ";
        sortare.pop();
    }
}

void Graph::generateFromSecventa(char *file_in, char *file_out){
    ifstream f(file_in);
    ofstream g(file_out);

    vector<int> values;
    int number_of_values;

    f>>number_of_values;
    values.resize(number_of_values + 1);

    for(int i = 1; i <= number_of_values; i++){
        int grad;
        f>>grad;
        values[i] = grad;
    }

    if(this->hakimi(values,number_of_values)) g<<"DA";
    else g<<"NU";
}

void Graph::print_Critical_Edges(char *file){
    ofstream g(file);

    vector<vector<int>> critical_edges;

    critical_edges = this->Find_Critical_Edges();

    g<<"Numar muchii critice: "<<critical_edges.size()<<"\n";

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

        for(int j = 0; j<critical_edges[i].size(); j++){
            g<<critical_edges[i][j]<<" ";
        }

        g<<"\n";
    }
}

void Graph::print_APM(char *file){
    ofstream g(file);

    int cost_APM = 0;
    vector<pair<int, int>> APM_edges;

    APM_edges = create_APM(cost_APM);

    g<<cost_APM<<"\n";

    g<<this->graph_Nodes - 1<<"\n";

    for(int i = 0; i < this->graph_Nodes - 1; i++){
        g<<APM_edges[i].first<<" "<<APM_edges[i].second<<"\n";
    }
}

//METODELE PRIVATE:
                //CITIREA BFS INFOARENA - CITIREA UNUI GRAF ORIENTAT FARA COSTURI CE CUPRINDE SI NODUL SURSA DE LA CARE SE VOR CALCULA DRUMURILE MINIME
int Graph::read_BFS_Infoarena(char *file){
    ifstream f(file);

    vector<int> aux;
    int nrMuchii, nodSursa;

    f>>this->graph_Nodes;
    this->graph_adjacency_list.assign(this->graph_Nodes + 1, aux);

    f>>nrMuchii;

    f>>nodSursa;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->graph_adjacency_list[x].push_back(y);
    }
    return nodSursa;
}

vector<int>Graph::create_Minimum_Paths(int nod){
                //initializam vectorul de distante minime

    vector<int> distante;
    distante.assign(this->graph_Nodes + 1, 0);

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

            //initial toate nodurile sunt nevizitate, asaa ca initializam viz[orice nod] = 0
    vector<int> viz;
    viz = this->initViz();

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

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

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

        curent = coada.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->graph_adjacency_list[curent].size(); i++){

            if(viz[this->graph_adjacency_list[curent][i]] == 0){
                coada.push(this->graph_adjacency_list[curent][i]);

                distante[coada.back()] = distante[curent]+1;

                viz[this->graph_adjacency_list[curent][i]] = 1;
            }
        }

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

    return distante;
}

void Graph::print_Minimum_Paths(char *file, vector<int> distances){
    ofstream g(file);

    for(int i=1; i <= this->graph_Nodes; i++){
        g<<distances[i] - 1<<" ";
    }
}

        //crearea vectorului cu nodurile nevizitate
vector<int>Graph::initViz(){
    vector<int> viz;
    viz.assign(this->graph_Nodes + 1, 0);
    return viz;
}

        //numararea componentelor conexe
int Graph::count_Connected_Components(){
            //numarul componentelor conexe il vom tine in nr
    int nr = 0;

            //initial toate nodurile sunt nevizitate
    vector<int> viz;
    viz = this->initViz();

    //pentru fiecare nod nevizitat parcurgem din copil in copil prin DFS; de fiecare data cand dam de un nod nevizitat inseamna ca avem o noua componenta conexa

    for(int nod = 1; nod <= this->graph_Nodes; nod++){
        if(viz[nod] == 0){
            nr++;
            DFS(nod,viz);
        }
    }

    return nr;
}

vector<unordered_set<int>>Graph::create_Biconnected_Components(){
    vector<unordered_set<int>> biconnected_components;
    stack<pair <int, int>> StivaMuchiiComponentaBiconexaCurenta;

    vector<int> vizPasi;
    vector<int> low_link_values;

    vizPasi.assign(this->graph_Nodes + 1, -1);
    low_link_values.resize(this->graph_Nodes + 1);

    DFSBiconnected(1,0,0,vizPasi,low_link_values,biconnected_components,StivaMuchiiComponentaBiconexaCurenta);

    return biconnected_components;
}


void Graph::DFSBiconnected(int nodCurent, int precedent, int pas, vector<int>& vizPasi, vector<int>& low_link_values,vector<unordered_set<int>>& biconnected_components,stack<pair <int, int>>& StivaMuchiiComponentaBiconexaCurenta){
    //marcam ca vizitat nodul curent
    vizPasi[nodCurent] = pas;

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

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

        if(vecinCurent != precedent){
            //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(vizPasi[vecinCurent] == -1){

                //am dat de o noua muchie din componenta biconexa curenta, asa ca o adaugam in stiva
                StivaMuchiiComponentaBiconexaCurenta.push(make_pair(nodCurent, vecinCurent));

                //apelam DFS pentru vecinul curent
                DFSBiconnected(vecinCurent, nodCurent, pas + 1,vizPasi,low_link_values,biconnected_components,StivaMuchiiComponentaBiconexaCurenta);

                //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[nodCurent] > low_link_values[vecinCurent]){
                    low_link_values[nodCurent] = low_link_values[vecinCurent];
                }

                //verificam daca am ajuns la finalul componentei biconexe

                if(low_link_values[vecinCurent] >= vizPasi[nodCurent]){
                    //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 = StivaMuchiiComponentaBiconexaCurenta.top().first;
                        aux2 = StivaMuchiiComponentaBiconexaCurenta.top().second;

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

                        StivaMuchiiComponentaBiconexaCurenta.pop();

                    } while (aux1 != nodCurent || aux2 != vecinCurent);

                    biconnected_components.push_back(aux);
                }
            }else{
                //avem o muchie de intoarcere, trebuie sa verificam daca nu cumva duce mai sus

                if(low_link_values[nodCurent] > vizPasi[vecinCurent]){
                    low_link_values[nodCurent] = vizPasi[vecinCurent];
                }
            }
        }
    }
}

vector<vector<int>>Graph::Create_Strongly_Connected_Components(){
    vector<vector<int>> strongly_connected_components;

    stack<int> StivaComponentaTareConexaCurenta;
    int arrivalTimeCurent = 0;

    vector<int> isInStiva;
    isInStiva.assign(this->graph_Nodes + 1, 0);

    vector<int> arrivalTime;
    arrivalTime.assign(this->graph_Nodes + 1, -1);

    vector<int> lowLinkValue;
    lowLinkValue.resize(this->graph_Nodes + 1);

    for(int i=1; i<=this->graph_Nodes; i++){
        if(arrivalTime[i] == -1){
            tarjan(i,StivaComponentaTareConexaCurenta,isInStiva,arrivalTime, arrivalTimeCurent,lowLinkValue,strongly_connected_components);
        }
    }

    return strongly_connected_components;
}


void Graph::tarjan(int nod,stack<int>& StivaComponentaTareConexaCurenta,vector<int>& isInStiva,vector<int>& arrivalTime, int& arrivalTimeCurent, vector<int>& lowLinkValue, vector<vector<int>>& strongly_connected_components){
    //adaugam nodul in componenta tare conexa curenta, adica in StivaComponentaTareConexaCurenta
    StivaComponentaTareConexaCurenta.push(nod);

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

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

    lowLinkValue[nod] = arrivalTimeCurent;

    //marim timpul de ajungere pentru urmatorul pas
    arrivalTimeCurent++;

    //parcurgem vecinii nodului curent, facand un DFS

    for(int i=0; i<this->graph_adjacency_list[nod].size(); i++){
        int vecinCurent = this->graph_adjacency_list[nod][i];

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

            tarjan(vecinCurent,StivaComponentaTareConexaCurenta,isInStiva,arrivalTime, arrivalTimeCurent,lowLinkValue,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(lowLinkValue[vecinCurent] < lowLinkValue[nod]){
                lowLinkValue[nod] = lowLinkValue[vecinCurent];
            }

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

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

                if(lowLinkValue[vecinCurent] < lowLinkValue[nod]){
                    lowLinkValue[nod] = lowLinkValue[vecinCurent];
                }
            }
        }
    }
    //verificam daca nodul curent inchide o componenta tare conexa
    if(arrivalTime[nod] == lowLinkValue[nod]){
        //trebuie sa mutam componenta tare conexa curenta din stiva in vectorul cu toate componentele tare conexe din graf
        vector<int> aux;
        int nodAux;

        do{

            nodAux = StivaComponentaTareConexaCurenta.top();

            aux.push_back(nodAux);

            StivaComponentaTareConexaCurenta.pop();
            isInStiva[nodAux] = 0;

        }while(nodAux != nod);

        strongly_connected_components.push_back(aux);
    }
}

void Graph::DFSSortareTopologica(int nod, vector<int>& viz, stack<int>& sortare){

    viz[nod] = 1;

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

        int vecinCurent = this->graph_adjacency_list[nod][i];

        if(viz[vecinCurent] == 0){
            DFSSortareTopologica(vecinCurent, viz, sortare);
        }
    }
    sortare.push(nod);
}

bool Graph::hakimi(vector<int>& values, int number_of_values){
    int suma = 0;

    sort(values.begin()+1, values.end(), greater<int>());

    while(values[0] > 0){
        int gradCurent = values[0];

        suma = suma + gradCurent;

        if(gradCurent > number_of_values - 1){
            return false;
        }

        values.erase(values.begin() + 0);

        for(int i=1; i<=gradCurent; i++){
            values[i]--;
            if(values[i]<0){
                return false;
            }
        }
    }

    if(values[0] == 0 && suma % 2 == 0) return true;

    return false;
}

vector<vector<int>> Graph::Find_Critical_Edges(){
    int arrivalTimeCurent = 0;
    vector<vector<int>> vectorMuchiiiCritice;

    vector<int> viz;
    viz = this->initViz();

    vector<int> prec;
    prec.resize(this->graph_Nodes + 1);

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

    vector<int> arrival_times;
    arrival_times.assign(this->graph_Nodes + 1, -1);

    for(int i = 1; i <= this->graph_Nodes; i++){
        if(viz[i] == 0){
            DFSCriticals(i, arrivalTimeCurent,vectorMuchiiiCritice, viz, arrival_times, low_link_values, prec);
        }
    }

    return vectorMuchiiiCritice;
}

void Graph::DFSCriticals(int nodCurent, int& pas, vector<vector<int>>& critical_edges, vector<int>& viz, vector<int>& arrivalTimes, vector<int>& lowLinkValues, vector<int>& prec){
    //marcam nodul ca vizitat in vectorul viz, actualizam timpul lui de ajungere iar low link value momentan e fix timpul de ajungere

    viz[nodCurent] = 1;

    arrivalTimes[nodCurent] = pas;

    lowLinkValues[nodCurent] = pas;
    //crestem timpul de ajungere pentru urmatorul DFS
    pas++;

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

        int vecinCurent = graph_adjacency_list[nodCurent][i];

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

            DFSCriticals(vecinCurent, pas,critical_edges,viz,arrivalTimes,lowLinkValues,prec);

            //la iesirea din DFS incercam sa minimizam low link value pentru nodul curent, in cazul in care vecinul poate ajunge la un nod mai indepartat
            if(lowLinkValues[nodCurent] > lowLinkValues[vecinCurent]){
                lowLinkValues[nodCurent] = lowLinkValues[vecinCurent];
            }

            //in cazul in care este o muchie critica, o adaugam in vectorul de muchii critice
            if (lowLinkValues[vecinCurent] > arrivalTimes[nodCurent]){
                critical_edges.push_back({nodCurent,vecinCurent});
            }
        }
        else{
            //pentru fiecare vecin deja vizitat incercam sa minimzam low link value pentru nodul nostru

            if (vecinCurent != prec[nodCurent]){
                if(lowLinkValues[nodCurent] > arrivalTimes[vecinCurent]){
                    lowLinkValues[nodCurent] = arrivalTimes[vecinCurent];
                }
            }
        }
    }
}

vector<pair<int,int>> Graph::create_APM(int &cost_APM) {
    vector<pair<int,int>> APM_edges;

    vector<int> vec;
    vector<int> poz;
    vector<int> distante;
    vector<int> heap;


    distante.assign(this->graph_Nodes + 1, 200000200);

    vec.assign(this->graph_Nodes + 1, 0);
    poz.assign(this->graph_Nodes + 1, 0);
    heap.push_back(0);

    distante[1] = 0;

    introduce_in_APM(1,distante,vec);

    for(int i = 2; i <= this->graph_Nodes; i++){
        introduce_in_min_heap(i,heap,poz,distante);
    }

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

        rad = extract_root_min_heap(heap,poz,distante);

        introduce_in_APM(rad,distante,vec);

        cost_APM = cost_APM + distante[rad];

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

        for(int j = 0; j < this->graph_adjacency_list_with_costs[rad].size(); j++){
            int nod;
            nod = this->graph_adjacency_list_with_costs[rad][j].first;
            if(poz[nod]) pop(poz[nod],heap,poz,distante);
        }
    }

    return APM_edges;
}

void Graph::introduce_in_APM(int nod, vector<int>& distante, vector<int>& vec) {
    for(int i = 0; i < this->graph_adjacency_list_with_costs[nod].size(); i++){
        int vecin, cost;

        vecin = this->graph_adjacency_list_with_costs[nod][i].first;
        cost = this->graph_adjacency_list_with_costs[nod][i].second;

        distante[vecin] = min(distante[vecin],cost);

        if(distante[vecin] == cost) vec[vecin] = nod;
    }
}

void Graph::introduce_in_min_heap(int nod, vector<int>& heap, vector<int>& poz, vector<int> distante) {
    heap.push_back(nod);
    poz[nod] = heap.size() - 1;
    pop(heap.size() - 1,heap,poz,distante);
}

int Graph::extract_root_min_heap(vector<int>& heap,vector<int>& poz, vector<int> distante) {
    int rad;

    rad = heap[1];

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

    heap.pop_back();

    push(1,heap,poz,distante);

    poz[rad] = 0;

    return rad;
}

void Graph::pop(int index, vector<int>& heap, vector<int>& poz, vector<int>& distante) {
    while(index > 1 && distante[heap[index]] < distante[heap[index / 2]]){
        swap(heap[index], heap[index / 2]);
        swap(poz[heap[index]], poz[heap[index / 2]]);
        index = index / 2;
    }
}

void Graph::push(int index, vector<int>& heap, vector<int>& poz, vector<int>& distante) {
    while((index * 2 <= heap.size() - 1 && distante[heap[index]] > distante[heap[index * 2]]) ||
           (index * 2 + 1 <= heap.size() - 1 && distante[heap[index]] > distante[heap[index * 2 + 1]])){

        if(distante[heap[index * 2]] < distante[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;
        }

    }
}

int main() {
                    /*BFS INFOARENA*/
    /*Graph g;

    g.show_Shortest_Paths("../bfs.in","../bfs.out");*/

                    /*DFS INFOARENA*/
    /*Graph g;

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

    g.print_Number_Of_Connected_Components("../dfs.out");*/

                    /*COMPONENTE BICONEXE INFOARENA*/

    /*Graph g;

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

    g.print_Biconnected_Components("../biconex.out");*/



                /*COMPONENTE TARE CONEXE INFOARENA*/

    /*Graph g;

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

    g.print_Strongly_Connected_Components("../ctc.out");*/

            /*SORTARE TOPOLOGICA INFOARENA*/

    /*Graph g;

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

    g.print_Topological_Sort("../sortaret.out");*/

                /*HAVEL HAKIMI*/
    /*Graph g;
    g.generateFromSecventa("../hakimi.in","../hakimi.out");*/

                /*MUCHII CRITICE GRAF NEORIENTAT LEETCODE*/
    /*Graph g;

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

    g.print_Critical_Edges("../critice.out");*/

            /*APM - ALGORITMUL LUI PRIM*/

    Graph g;

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

    g.print_APM("../apm.out");
    return 0;
}