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

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

int S,N,M,start[100002],k,x,y,viz[100002],pr,ul,i,coada[100002];

struct vecin
{
    int v,urm;
};

vecin L[1000002];
int main()
{
    f>>N>>M>>S;
    k=0;
    for(i=1;i<=M;i++)
    {
        f>>x>>y;
        k++;
        L[k].v=y;
        L[k].urm=start[x];
        start[x]=k;
    }
    for(i=1;i<=N;i++)
    {
        viz[i]=-1;
    }
    coada[1]=S;
    pr=1;
    ul=1;
    viz[S]=0;
    while(pr<=ul)
    {
        x=coada[pr];
        pr++;
        for(i=start[x];i!=0;i=L[i].urm)
        {
            y=L[i].v;
            if(viz[y]==-1)
            {
                viz[y]=1+viz[x];
                ul++;
                coada[ul]=y;
            }
        }
    }
    for(i=1;i<=N;i++)
    {
        g<<viz[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}