#include <cstdio>
#include <cstdlib>

FILE*f=fopen("bfs.in","r");
FILE*g=fopen("bfs.out","w");

int a[3][100001];
int b[100001],i,m,n,s,ok;

int main()
{
    fscanf(f,"%d%d%d",&n,&m,&s);
    for (i=1;i<=m;i++)
        fscanf(f,"%d%d",&a[1][i],&a[2][i]);
    b[s]=1;
    ok=1;
    while (ok)
    {
          ok=0;
          for (i=1;i<=m;i++)
              if (b[a[1][i]]!=0 && (b[a[2][i]]==0 || b[a[2][i]]>b[a[1][i]]+1))
              {
                   b[a[2][i]]=b[a[1][i]]+1;
                   ok=1;
                   }
          }
    for (i=1;i<=n;i++)
        fprintf(g,"%d ",b[i]-1);
    return 0;
}