#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(int N, int M, bool orientat,const vector<pair<int,int>> &muchii);///constructor pentru alte probleme
    ~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(int N, int M, bool orientat,const vector<pair<int,int>> &muchii)
{
    nrNoduri = N;
    nrMuchii = M;
    lsAd.resize(nrNoduri+1);

    for (auto muchie : muchii)
        {
            lsAd[muchie.first].push_back(muchie.second);
            if (!orientat)
                lsAd[muchie.second].push_back(muchie.first);
        }
}
void Graf::DFS(char* fisierIesire)
{
    stack<int> stiva;

    int nrComponente = 0;
    set<int> noduriNemarcate;

    for (int i = 1; i <= nrNoduri; i++)
        noduriNemarcate.insert(i);

    while (!noduriNemarcate.empty())
    {
        stiva.push(*(noduriNemarcate.begin()));///adaug nodul nevizitat in stiva
        noduriNemarcate.erase(*(noduriNemarcate.begin()));///si il sterg din multimea de nevizitate

        int nodCrt;

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

            for (auto nodAd : lsAd[nodCrt])
            {
                if (noduriNemarcate.find(nodAd)!= noduriNemarcate.end())
                {
                    noduriNemarcate.erase(nodAd);
                    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");
    int n, m, x, y;
    vector<pair<int,int>> muchii;

    in>>n>>m;

    for (int i = 0; i < m; i++)
    {
        in>>x>>y;
        muchii.push_back(make_pair(x,y));
    }
    in.close();

    Graf g(n,m,false,muchii);
    g.DFS("dfs.out");

}