#include <bits/stdc++.h>

using namespace std;




class Graf
{
    int nrNoduri;
    int nrMuchii;
    int s_bfs;  ///nodul s din exercitiul bfs
    vector<vector<int>> lsAd; ///lista de adiacenta a grafului

public:
    Graf(char* fisierIntrare={"bfs.in"});///constructor pentru problema bfs
    Graf(bool orientat,ifstream &in);///constructor pentru exercitiul DFS (si poate altele)
    ~Graf();

    void BFS(char* fisierIesire={"bfs.out"});///primul exercitiu(afiseaza intr-un fisier lungimea drumurilor de la un nod la restul)
    void DFS(char* fisierIesire="dfs.out");
};

Graf::Graf(char* fisierIntrare)
{
    ifstream in(fisierIntrare);
    int x, y;

    in>>nrNoduri>>nrMuchii>>s_bfs;
    lsAd.resize(nrNoduri+1); ///un fel de initializare a listei de adiacenta in constructor

    for (int i = 0; i < nrMuchii; i++)
    {
        in>>x>>y;
        lsAd[x].push_back(y);
    }
    in.close();
}

Graf::~Graf()
{
    lsAd.clear();
}

Graf::Graf(bool orientat,ifstream &in)
{
    int x, y;

    in>>nrNoduri>>nrMuchii;
    lsAd.resize(nrNoduri+1);

    for (int i = 0; i < nrMuchii; i++)
        {
            in>>x>>y;
            lsAd[x].push_back(y);
            if (!orientat)
               lsAd[y].push_back(x);
        }
}
void Graf::DFS(char* fisierIesire)
{
    stack<int> stiva;

    int nrComponente = 0;
    bool* nodMarcat = new bool[nrNoduri+1]();///initializat cu false pentru toate nodurile

    for (int i = 1; i <= nrNoduri; i++)
    {
        if (!nodMarcat[i])
            {
                stiva.push(i);
                nodMarcat[i] = true;
                int nodCrt;

                while (!stiva.empty())
                {
                    nodCrt = stiva.top();
                    stiva.pop();

                    for (auto nodAd : lsAd[nodCrt])
                    {
                        if (!nodMarcat[nodAd])
                        {
                            nodMarcat[nodAd] = true;
                            stiva.push(nodAd);
                        }
                    }
                }
                nrComponente++;
            }
    }

    ///scrierea in fisier
    ofstream out(fisierIesire);
    out<<nrComponente;
    out.close();
}


void Graf::BFS(char* fisierIesire)
{
    queue<int> coada;

    bool* nodVizitat = new bool[nrNoduri+1];///array-ul cu care verific daca a fost vizitat un nod
    int* distNod = new int[nrNoduri+1];///nr muchii catre fiecare nod

    for (int i = 1; i <= nrNoduri; i++)
        {
            distNod[i] = (i == s_bfs ? 0 : -1);
            nodVizitat[i] = false;
        }

    coada.push(s_bfs);
    int nodCrt;///nodul curent din parcurgerea laterala
    while(!coada.empty())
    {
        nodCrt = coada.front();
        coada.pop();
        nodVizitat[nodCrt] = true;

        for (int i = 0; i < lsAd[nodCrt].size(); i++)///trec prin toate nodurile adiacente
        {
            if (!nodVizitat[lsAd[nodCrt][i]])///daca nodul este nevizitat il adaug in coada
            {
                distNod[lsAd[nodCrt][i]] = distNod[nodCrt]+1;
                nodVizitat[lsAd[nodCrt][i]] = true; ///buba care mi-a dat 80 pct
                coada.push(lsAd[nodCrt][i]);
            }
        }
    }

    ///scrierea in fisier
    ofstream out(fisierIesire);

    for (int i = 1; i <= nrNoduri; i++)
        out<<distNod[i]<<' ';
    out.close();
    delete[] distNod;
    delete[] nodVizitat;
}


int main()
{
    ///pentru BFS
//    Graf g;
//    g.BFS();

    ///pentru DFS
    ifstream in("dfs.in");
    Graf g(false,in);
    g.DFS("dfs.out");

}