#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
int n,*a[100000],d[100000];

void parcurge(int s)
{int x,i,in,sf=in=0,q[100000];
d[s]=1;
q[0]=s;
while(in<=sf)
{x=q[in++];
for(i=1;i<=a[x][0];i++)
    if(!d[a[x][i]])
{d[a[x][i]]=d[x]+1;
  q[++sf]=a[x][i];
}
}

for(i=1;i<=n;i++)d[i]--;
}


int main()
{int i,s,m,v,b;

ifstream fin("bfs.in");
ofstream fout("bfs.out");
    fin>>n>>m>>s;
 for(i=1;i<=n;i++)
    {a[i]=(int*)realloc(a[i],sizeof(int));
    a[i][0]=0;}


for(i=1;i<=m;i++)
{fin>>v>>b;
a[v][0]++;
a[v]=(int*)realloc(a[v],(a[v][0]+1)*sizeof(int));
a[v][a[v][0]]=b;
}

parcurge(s);

 for(i=1;i<=n;i++)
    fout<<d[i]<<' ';

}