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

ifstream in("bfs.in");
ofstream out("bfs.out");

class graf
{
    int n, m;
public:
    queue <int> coada;
    vector <int> lista_adiacenta[100005]; //in acest mod va fi stocat graful
    int distanta[100005]; //vectorul de distante minime
    int get_n();
    int get_m();
    void set_n(int);
    void set_m(int);
    graf(int, int);
    void construire_graf();
    void bfs(int);
};

int graf :: get_n()
{
    return this->n;
}

int graf :: get_m()
{
    return this->m;
}

void graf :: set_n(int n)
{
    this->n = n;
}

void graf :: set_m(int m)
{
    this->m = m;
}

graf::graf(int n, int m)
{
    this -> n = n;
    this -> m = m;
    for(int j = 1; j < 100005; j++)
        distanta[j]=-1; //initial vectorul de distante contine -1 si anume nu se poate ajunge din nodul s in alt nod
}

void graf :: construire_graf()
{
    for(int i = 0; i <= m-1; i++) //parcurgem muchiile
    {
        int u, v;
        in >> u >> v; //citim nodurile intre care exista muchie
        lista_adiacenta[u].push_back(v); //adaugam in lista de adiacenta
    }
}

void graf :: bfs(int nod_s)
{
    coada.push(nod_s); //initial in coada va fi nodul s
    distanta[nod_s]=0; //distanta min de la un nod la el insusi e 0
    while(!coada.empty())
    {
        nod_s = coada.front();
        coada.pop();
         for(int i = 0; i < lista_adiacenta[nod_s].size(); i++) //parcurgem lista de adiacenta a noddului nod_s
         {
            if(distanta[lista_adiacenta[nod_s][i]] == -1)
            {
                distanta[lista_adiacenta[nod_s][i]] = distanta[nod_s] + 1; //se actualizeaza vectorul de distanta
                coada.push(lista_adiacenta[nod_s][i]); //se adauga in coada vecinul i al nodului_s
            }
         }

    }
}

int main()
{
    int s, n, m;
    in >> n >> m >> s; //se citesc nr. de noduri, nr. de muchii si nodul dat
    graf G(n, m); //se apeleaza constructorul
    G.construire_graf(); //se apeleaza functia de construire a grafului
    G.bfs(s); //se apeleaza metoda bfs
    for(int k = 1; k <= G.get_n(); k ++)
        out << G.distanta[k] << " "; //se afiseaza rezultatul

    return 0;
}