#include <bits/stdc++.h>
using namespace std;

class Graf
{
private:
    int nrNoduri;
    int nrMuchii;
    vector<vector<int>> lisAdiacenta;

public:
    Graf(int nrNoduriDat, int nrMuchiiDat);
    Graf(int nrNoduriDat, int nrMuchiiDat, vector<vector<int>> &listaData);
    Graf(const Graf &grafDat);
    ~Graf();

    vector<vector <int>> getLisAdiacenta();
    int getNrNoduri();
    int getNrMuchii();

    Graf& operator= (const Graf &grafDat);
    friend std::ostream& operator<<(std::ostream &out, const Graf &grafDat);

    void citireOrientat(istream &in);
    void citireNeorientat(istream &in);

    vector<int> BFS(int nodStart);
    void afisareDistanteBFS(int nodStart, ostream &out);
    void DFS(int nodStart, vector<bool> &vizitat);
    int nrCompConexe();
};

Graf :: Graf(int nrNoduriDat, int nrMuchiiDat)  //constructor parametrizat - nu avem lista de adiacenta
{
     nrNoduri = nrNoduriDat;
     nrMuchii = nrMuchiiDat;

     vector<int> aux(1,-1);       //initializam prima pozitie cu -1 pentru ca indexarea e de la 1
     for(int i = 0; i <= nrNoduri+1; ++i){
         lisAdiacenta.push_back(aux);
     }
}

Graf :: Graf(int nrNoduriDat, int nrMuchiiDat, vector<vector<int>> &listaData)  //constructor parametrii - avem lista adiacenta
{
     nrNoduri = nrNoduriDat;
     nrMuchii = nrMuchiiDat;
     lisAdiacenta = listaData;
}

Graf :: Graf(const Graf & grafDat)   //constructor copiere
{
     nrNoduri = grafDat.nrNoduri;
     nrMuchii = grafDat.nrMuchii;
     lisAdiacenta = grafDat.lisAdiacenta;
}

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

//_____________________________________________

vector<vector <int>> Graf :: getLisAdiacenta()  //getter lista adiacenta
{
     return lisAdiacenta;
}

int Graf :: getNrNoduri()    //getter numar noduri
{
     return nrNoduri;
}

int Graf :: getNrMuchii()    //getter numar muchii
{
     return nrMuchii;
}

Graf& Graf :: operator= (const Graf &grafDat) //supraincarcare operator egal
{
    if(this != &grafDat) {
        this->nrNoduri = grafDat.nrNoduri;
        this->nrMuchii = grafDat.nrMuchii;

        if(!this->lisAdiacenta.empty())
            lisAdiacenta.clear();

        this->lisAdiacenta = grafDat.lisAdiacenta;
    }

    return *this;
}


ostream& operator<< (std::ostream& out, const Graf& grafDat)  //supraincarcare operator afisare
{
    out << "Numarul de noduri ale grafului este: " << grafDat.nrNoduri << "\n";
    out << "Numarul de muchii ale grafului este: " << grafDat.nrMuchii << "\n";

    for (int i = 1; i < grafDat.nrNoduri; ++i){
         for (int j = 1; j < grafDat.lisAdiacenta[i].size(); ++j){
             out<< grafDat.lisAdiacenta[i][j]<<" ";
        }
        out<<"\n";
    }

    return out;
}

//_____________________________________________

void Graf :: citireNeorientat(istream &in)  //citim de la tastatura sau din fisier un graf neorientat
{
    int x, y;

    for (int i = 1; i <= nrMuchii; ++i){
            in >> x >> y;
            lisAdiacenta[x].push_back(y), lisAdiacenta[y].push_back(x);
        }
}


void Graf :: citireOrientat(istream &in)   //citim de la tastatura sau din fisier un graf orientat
{
    int x, y;

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

//_____________________________________________

vector<int> Graf :: BFS(int nodStart)     //parcurgere in latime
{
    queue<int> Q;
    int x, y;
    vector<int> distanta(nrNoduri+1, -1);

    distanta[nodStart] = 0;
    Q.push(nodStart);

    while(!Q.empty()){
            x = Q.front();   //eliminam nodul curent din coada
            Q.pop();

            for (int i = 1; i < lisAdiacenta[x].size(); ++i)
                if (distanta[lisAdiacenta[x][i]] == -1){               //daca nu a fost vizitat vecinul
                    distanta[lisAdiacenta[x][i]] = distanta[x] + 1;    //inseamna ca am gasit drum mai scurt
                    Q.push(lisAdiacenta[x][i]);
                }
        }

    return distanta;
}

void Graf :: afisareDistanteBFS(int nodStart, ostream &out)   //afisam vectorul de distante de la BFS
{
    vector <int> distanta = BFS(nodStart);

    for(int i = 1; i <= nrNoduri; ++i)   {
             out << distanta[i] << " ";
        }
}


void Graf :: DFS(int x, vector<bool> &vizitat)   //parcurgere in adancime
{
    vizitat[x] = 1;

    for(int i = 1; i < lisAdiacenta[x].size(); i++)
        if(vizitat[lisAdiacenta[x][i]] == 0)    //daca vecinul sau nu a fost vizitat, mergem la el
            DFS(lisAdiacenta[x][i], vizitat);
}

int Graf :: nrCompConexe()   //numar de componente conexe facut cu DFS
{
    int nrCompCon = 0;
    vector<bool> vizitat(nrNoduri+1, 0);

    for(int i = 1; i <= nrNoduri; ++i )
        if(!vizitat[i]){
            nrCompCon++;
            DFS(i, vizitat);
    }

    return nrCompCon;
}

///_______________________________________________________

void Rezolva_DFSComponenteConexe()   //https://infoarena.ro/problema/dfs - 100pc
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");

    int N, M;
    fin >> N >> M;

    Graf graf(N, M);
    graf.citireNeorientat(fin);

    fout<<graf.nrCompConexe();
}

void Rezolva_BFS()  //https://www.infoarena.ro/problema/bfs - 100pc
{
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int N, M, S;
    fin >> N >> M >> S;

    Graf graf(N, M);
    graf.citireOrientat(fin);

    graf.afisareDistanteBFS(S, fout);
}


int main()
{
    Rezolva_BFS();
    return 0;
}