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

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

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

//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 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:Unoriented_graph{
private:
    vector< vector<int> > m_costs_matrix;
public:
    void read_graph(char *file);
    vector< pair<int,int> > prim(int &cost_APM);
    int get_number_of_nodes();

private:
    void introduce_in_APM(int node, vector<int>& distances, vector<int>& vec);

    void introduce_in_min_heap(int node, vector<int>& heap, vector<int>& poz, vector<int> distances);

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

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

    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<int> aux;
    int number_of_edges;

    f>>this->m_number_of_nodes;

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

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

    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(y);
        m_adjancency_list[y].push_back(x);

        m_costs_matrix[x][y] = cost;
        m_costs_matrix[y][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> poz;
    vector<int> distances;
    vector<int> heap;


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

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

    distances[1] = 0;

    introduce_in_APM(1, distances, vec);

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

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

        rad = extract_root_min_heap(heap, poz, distances);

        introduce_in_APM(rad, distances, vec);

        cost_APM = cost_APM + distances[rad];

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

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

    return APM_edges;
}

int Unoriented_graph_with_costs::get_number_of_nodes() {
    return this->m_number_of_nodes;
}

//METODE PRIVATE UNORIENTED GRAPH WITH COSTS

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

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

        neighbor = this->m_adjancency_list[node][i];
        cost = m_costs_matrix[node][neighbor];

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

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

void Unoriented_graph_with_costs::introduce_in_min_heap(int node, vector<int> &heap, vector<int> &poz,
                                                        vector<int> distances) {

    heap.push_back(node);
    poz[node] = heap.size() - 1;
    pop(heap.size() - 1, heap, poz, distances);
}

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

    root = 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, distances);

    poz[root] = 0;

    return root;
}

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

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

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

        index = index / 2;
    }
}

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

    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]])){

        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:Oriented_graph{
private:

};

//CLASA RETELE DE TRANSPORT

class Flow_network:Oriented_graph{
private:

};

//CLASA MULTIGRAF

class Multigraph:Graph{
private:

};

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

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

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

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

    for(it = v.begin(); 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){
    ofstream g(file);
    vector< vector<int> >::iterator it;
    vector<int>::iterator it_u;

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

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

        for(it_u = it->begin(); 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();
    }
}

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");*/

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

    g.read_graph("../apm.in");
    cost_apm = 0;

    apm = g.prim(cost_apm);

    out << cost_apm << "\n";

    out<<g.get_number_of_nodes() - 1<<"\n";

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

    return 0;
}