#include <iostream>
#include <fstream>
#include <vector>

#define nmax 100010

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int N , M , S , cost[ nmax ] , tata[ nmax ];
vector < int > A[ nmax ];
void bfs ( int k )
{
	for( int i = 0 ; i <= N ; ++i )// initializam cu -1 pt nodurile izolate
		cost[ i ]= -1;
	
	int lungime = 1;
	
	cost[ k ] = 0;// radacina are costul 0
	tata[ 1 ] = k;//primul fiu este chiar radacina k
	
	for( int i = 1 ; i <= lungime ; ++i )//parcurgem vectorul tatii( nodurile deja introduse in sir si deja verificate)
		for(unsigned  int j = 0 ; j < A[ tata[ i ] ].size( ) ; ++j )// parcurgem toti fii pt fiecare tata
		{
			int fiu = A[ tata[i] ][ j ];
			if( cost[ fiu ] == -1)// daca nu a mai fost verificat(daca a mai fost inseamna ca nu este drumul minim acesta)
			{
				lungime++;
				tata[ lungime ] = fiu;
				cost[ fiu ] = cost [ tata[i] ] + 1;
			}
		}
}


int main()
{
	f >> N >> M >> S;
	
	for( int i = 1 ; i <= M ; ++i )
	{
		int x , y;
		f >> x >> y;
		A[ x ].push_back( y );//arc de la nodul x la nodul y
	}
	
	bfs( S );
	
	for( int i = 1 ; i <= N ; i++ )
		g<< cost[ i ] << " ";
	
	f.close();
	g.close();
	
return 0;
}