#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

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

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

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

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

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


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");
    return 0;
}