#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int n,m,i,s,x,y,b;
queue<int> que;
struct nod {int inf;nod *next;} *a[100010],*p;
int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	vector<int> ut(n+1,-1);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		p=new nod;
		p->next=a[x];
		p->inf=y;
		a[x]=p;
	}
	que.push(s);ut[s]=0;
	while(!que.empty())
	{
		b=que.front();
		for(p=a[b];p;p=p->next)
			if(ut[p->inf]<0)
			{
				que.push(p->inf);
				ut[p->inf]=ut[b]+1;
			}
		que.pop();
	}
	for(i=1;i<=n;i++)
		printf("%d ",ut[i]);
	printf("\n");
	return 0;
}