#include <cstdio>
using namespace std;
struct graf
{
int x;
graf *u;
};
graf *a[100001];
int c[100001],d[100001];
int ultim,nr,s;
void bag(int x,int y)
{
graf *q=new graf;
q->x=y;
q->u=a[x];
a[x]=q;
}
void par(int x)
{
graf *q=a[x];
while(q!=NULL)
{
if((d[q->x]==0)&&(q->x!=s))
{
++ultim;
c[ultim]=q->x;
}
q=q->u;
}
}
int main()
{
short e=0;
int i,n,m,x,y;
freopen("bfs.in","r",stdin);
freopen("bfs.out","w",stdout);
scanf("%d%d%d",&n,&m,&s);
for(i=0;i<m;++i)
{
scanf("%d%d",&x,&y);
bag(x,y);
}
c[1]=s;
x=1;
y=1;
ultim=1;
while(e==0)
{
while(x<=y)
{
d[c[x]]=nr;
par(c[x]);
++x;
}
if(y==ultim) e=1;
else
{
y=ultim;
++nr;
}
}
for(i=1;i<n;++i)
if (d[i]==0)
{
if (i==s) printf("0 ");
else printf("-1 ");
}
else printf("%d ",d[i]);
if (d[n]==0)
{
if (n==s) printf("0\n");
else printf("-1\n");
}
else printf("%d\n",d[n]);
return 0;
}