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

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

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

    }
}

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

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

    return 0;
}