// Simionescu Andrei, -/-/2010
// http://infoarena.ro/problema/bfs
// Dificultate: - 
// Categorii: -

#include <cstdio>
#include <cstdlib>
using namespace std;

# define NMAX 100001

int n, *A[NMAX], D[NMAX], s;

// Read
void read ()
{
	freopen( "bfs.in", "r", stdin );
	int m;
	
    scanf( "%d %d %d", &n, &m, &s );
    
	for ( int i = 1; i <= n; ++i )	
	{	
		A[i]= new int;
		A[i][0]=0;
        D[i]=-1;
	}
	
	for ( ; m; --m )
	{
		int i, j;
		scanf( "%d %d", &i, &j );
		
		A[i][0]++;
		A[i]= (int *) realloc( A[i], ( A[i][0] + 2 ) * sizeof(int) );
		A[i][ A[i][0] ] = j;
	}
}

// Breadth search first
void bfs ()
{
	int * queue = new int[n + 1];
    int left = 1, right = 1, k, i;
	queue[left] = s;
	
    D[s] = 0;
	while( left <= right)
	{
		k = queue[ left++ ];
		for ( i = 1; i <= A[k][0]; ++i )
			if ( D[ A[k][i] ] == -1 )
			{
				queue[ ++right] = A[k][i];
				D[ A[k][i] ] = D[k] + 1;
			}
	}
}

// Write
void write ()
{
	freopen( "bfs.out", "w", stdout );
	
	for (int i = 1; i <= n; ++i )
		printf( "%d ", D[i] );
}

int main()
{
	read();
	bfs();
	write();
	
	return 0;
}