#include<stdio.h>
#include<vector>

using namespace std;

int sel[100002];
vector < vector < int> > muchii;
vector < int > coada_bf;

void bf( int start)
{
	
	coada_bf.push_back( start);
	sel[start ] = 0;
	for( int poz = 0; poz < coada_bf.size(); poz++)
	{
		int nr_vecini = muchii[ coada_bf[poz] ].size();
		for( int j = 0; j < nr_vecini ; ++j)
		{
			if( sel[ muchii[ coada_bf[poz]][j]] == -1)
			{
				sel[ muchii[ coada_bf[poz]][j]] = sel[ coada_bf[poz] ] + 1;
				coada_bf.push_back( muchii[ coada_bf[poz]][j]);
			}
		}
	}		
}


int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	
	
	int n,m,start;
	
	scanf("%d %d %d",&n,&m,&start);
	vector < int > temp;
	for( int i = 0; i <= n; ++i)
	{
		muchii.push_back(temp);
		sel[i] = -1;
	}
	
	for( long i = 1; i <= m; ++i)
	{
		int x,y;
		scanf("%d %d", &x, &y);
		muchii[x].push_back(y);
	
		
	}
	int sol = 0;
	
	bf(start);
	
	for( long i = 1; i < n; ++i)
	{
		printf("%d ", sel[i]);
	}
	printf("%d\n",sel[n]);
	
	
	
	return 0;
}