#include <stdio.h>
#include <deque>

using namespace std;
FILE *f,*g;
int start[1000002],t[3][2000004];
int drum[1000002];
deque <int> q;

int main()
{
    int x,i,j,m,n,o,k=0,nod,ss,no;
    f=fopen("bfs.in","r");
    g=fopen("bfs.out","w");
    fscanf(f,"%d %d %d",&n,&m,&x);
    for(o=1;o<=m;++o)
    {
        fscanf(f,"%d %d",&i,&j);
        ++k;
        t[0][k]=j;
        t[1][k]=start[i];
        start[i]=k;
    }
    for(i=1;i<=n;++i)
        drum[i]=2000000000;
    q.push_back(x);
    drum[x]=0;
    while(!q.empty())
    {
        nod=q.front();
        q.pop_front();
        no=start[nod];
        ss=drum[nod];
        while(no)
        {
            if(ss+1<drum[t[0][no]])
            {
                q.push_back(t[0][no]);
                drum[t[0][no]]=ss+1;
            }
            no=t[1][no];
        }
    }
    for(i=1;i<=n;++i)
    {
        if(drum[i]!=2000000000)
            fprintf(g,"%d ",drum[i]);
        else
            fprintf(g,"-1 ");
    }


    fclose(f);
    fclose(g);
    return 0;
}