#include <fstream>
#include <vector>
#define NMAX 100009
using namespace std;

FILE * fin =fopen("bfs.in", "r");
FILE * fout=fopen("bfs.out", "w");

int n, m, s;
int arce[NMAX], coada[NMAX];
vector<int>L[NMAX];

int main()
{
    int i, prim, ultim, a, b, vf;
    fscanf(fin, "%d %d %d\n", &n, &m, &s);
    for(i=1; i<=m; ++i)
    {
        fscanf(fin,"%d %d\n", &a, &b);
        L[a].push_back(b);
    }
    for(i=1; i<=n; ++i)
        arce[i]=-1;
    prim=ultim=0;
    coada[++ultim]=s;
    arce[s]=0;
    while(prim<=ultim)
    {
        vf=coada[++prim];
        for(i=0; i<L[vf].size(); ++i)
            if(arce[L[vf][i]]<0)
            {
                coada[++ultim]=L[vf][i];
                arce[L[vf][i]]=arce[vf]+1;
            }

    }
    for(i=1; i<=n; ++i)
        fprintf(fout, "%d ", arce[i]);
    fclose(fout);
    return 0;
}