#include <fstream>
#include <vector>
#define DMAX 100002
using namespace std;
FILE * fin = fopen ("bfs.in", "r");
FILE * fout = fopen ("bfs.out", "w");

void citire();
void rezolvare();
void afisare();

int n, m, s;
vector <int> lista[DMAX];
int drum[DMAX];

bool use[DMAX];
int coada[DMAX], prec[DMAX];

int main()
{
    
    citire();
    rezolvare();
    afisare();
    
    fclose(fin);
    fclose(fout);
    return 0;
}

void citire()
{
    int i, a, b;
    
    fscanf(fin, "%d %d %d", &n, &m, &s);
    for (i=1; i<=m; i++)
    {
        fscanf(fin, "%d %d", &a, &b);
        lista[a].push_back(b);
    }
    
    for (i=1; i<=n; i++) drum[i]=-1;
}

void rezolvare()
{
    int st=0, dr=0, vf, i;
    
    use[s]=1;
    coada[0]=s;
    drum[s]=0;
    
    while (st<=dr)
    {
        vf=coada[st++];
        for (i=0; i<lista[vf].size(); i++)
            if (!use[lista[vf][i]])
            {
                use[lista[vf][i]]=1;
                coada[++dr]=lista[vf][i];
                drum[lista[vf][i]]=drum[vf]+1;
            }
    }
}

void afisare()
{
    int i;
    for (i=1; i<=n; i++) fprintf(fout, "%d ", drum[i]);
}