#include<cstdio>
#include<queue>
using namespace std;
int v1[1000001],v2[1000001],x[100001],*ad[100001],w[100001];
int main()
{
	freopen("bfs.in","r",stdin);freopen("bfs.out","w",stdout);
	queue<int> q,p;int n,m,i,t,s=2,f,g;
	scanf("%d%d%d",&n,&m,&t);
	for(i=0;i<m;++i)
		scanf("%d%d",&v1[i],&v2[i]),x[v1[i]-1]++;
	for(i=0;i<n;x[i++]=0)
		ad[i]=new int[x[i]];
	for(i=0;i<m;++i)
		ad[v1[i]-1][x[v1[i]-1]++]=v2[i]-1;
	--t;
	w[t]=1;
	for(i=0;i<x[t];++i)
		q.push(ad[t][i]),p.push(1),w[ad[t][i]]=1;
	while(!q.empty())
	{
		f=q.front();g=p.front();
		for(i=0;i<x[f];++i)
			if(!w[ad[f][i]])
				q.push(ad[f][i]),p.push(g+1),w[ad[f][i]]=g+1;
		q.pop();p.pop();
	}
	for(i=0;i<t;++i)
		if(w[i])
			printf("%d ",w[i]);
		else
			printf("-1 ");
	printf("0 ");
	for(i=t+1;i<n;++i)
		if(w[i])
			printf("%d ",w[i]);
		else
			printf("-1 ");
}