#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

class Graf
{
   private:
       int nrN, nrM, start; ///Numar noduri, numar muchii, nod start BFS
       vector<int> listaAd[100002]; ///lista de adiacenta graf
   public:
       void citire(istream&);
       void afisare(ostream&);
       friend istream& operator>>(istream& in, Graf &g); ///supraincarcare operator >>
       friend ostream& operator<<(ostream& out, Graf &g); ///supraincarcare operator <<
       void BFS(ostream&);
};

void Graf :: citire(istream &in) ///citim graful
{
    in >> nrN;
    in >> nrM;
    in >> start;
    int st, dr;
    for (int i = 1; i <= nrM; i++)
    {
        in >> st >> dr;
        listaAd[st].push_back(dr);
    }
}

void Graf :: afisare(ostream &out)
{
    out << "Numar de noduri: " << nrN << "\n";
    out << "Numar de muchii: " << nrM << "\n";
    out << "Nodul de start BFS: " << start << "\n";
    for (int i = 0; i < nrN; i++)
        for (int j = 0; j < listaAd[i].size(); j++)
           {
               out << "Muchia "  << i << " " << listaAd[i][j];
               out << "\n";
           }
}

istream& operator>>(istream& in, Graf &g)
{
    g.citire(in);
    return in;
}

ostream& operator<<(ostream& out, Graf &g)
{
    g.afisare(out);
    return out;
}

void Graf :: BFS(ostream &out)
{
    int cost[nrN + 1], S;
    for (int i = 1; i < nrN + 1; i++)
        cost[i] = -1; ///initializam costurile cu -1
    queue <int> coada;
    coada.push(start); ///adaugam in coada nodul de start
    cost[start] = 0; ///costul pentru nodul de start este 0
    while (!coada.empty()) ///cat timp avem elemente in coada
    {
        S = coada.front();
        for (int i = 0; i < listaAd[S].size(); i++) ///parcurgem vecinii nodului curent
        {
            int nod_curent = listaAd[S][i];
            if (cost[nod_curent] == -1) ///daca e nevizitat
            {
                cost[nod_curent] = cost[S] + 1; ///actualizam costul
                coada.push(nod_curent); ///adaugam in coada vecinul
            }
        }
        coada.pop(); ///eliminam nodul curent din coada
    }
    for (int i = 1; i <= nrN; i++)
        out << cost[i] << " "; ///afisam costurile pentru fiecare nod
}

int main()
{
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    Graf g;
    fin >> g;
    g.BFS(fout);
    fin.close();
    fout.close();
    return 0;
}