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

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

//METODE PUBLICE

void Graph::read_graph(char *file) {
    return;
}


//CLASA UNORIENTED GRAPH

class Unoriented_graph:Graph{
protected:
    vector< vector<int> > m_adjancency_list;

};


//CLASA ORIENTED GRAPH

class Oriented_graph: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);
};

//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 adiacenta 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 nod 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 adiacenta 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 distante 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 nod] = 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 distante 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;
}

//CLASA UNORIENTED GRAPH WITH COSTS

class Unoriented_graph_with_costs:Unoriented_graph{
private:

};

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

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