#include<cstdio>
#include<cstring>
#include<vector>

#define maxn 100005
#define maxm 1000005

using namespace std ;

vector <int> vecini[maxn] ;

int n,m,s ;
int dist[maxn] ;
int coada[maxn] ;

void bf(int nod)
{
	int len = 1 ;
	coada[1] = nod ;
	for(int j=1;j<=len;++j)
	{	
		int nod_act = coada[j];
		for(size_t i=0;i<vecini[nod_act].size();++i)
		{
			if( dist[ vecini[ nod_act ][i] ] == -1 )
			{
				++ len ;
				coada[len] = vecini[ nod_act ][i] ;
				dist[ vecini[ nod_act ][i] ] = dist[nod_act] + 1 ;
			}	
		}
	}		
		
}

int main()
{
	
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	
	scanf("%d%d%d",&n,&m,&s);
	
	for(int i=1;i<=m;++i)
	{
		int a,b ;
		scanf("%d%d",&a,&b);
		vecini[a].push_back(b) ;
	}
	
	memset(dist,-1,sizeof(dist)) ;
	dist[s] =  0 ;
	
	bf(s) ;
	
	for(int i=1;i<n;++i)
		printf("%d ",dist[i]);
	printf("%d\n",dist[n]);
	
	return 0;
	
}