#include <fstream>
#include <queue>
#include <vector>
#define N 1<<17
using namespace std;
const char iname[] = "bfs.in";
const char oname[] = "bfs.out";
ifstream fin(iname);
ofstream fout(oname);
int n , m , s , i , j , x , y;
int cost[ N ];
vector <int> v[ N ];
queue <int> Q;
int main()
{
	fin >> n >> m >> s;
	for ( i = 1; i <= n; ++i ) cost[ i ] = N;
	for ( i = 1; i <= m; ++i )
	{
		fin >> x >> y;
		v[ x ].push_back( y );
	}
	cost[ s ] = 0;
	Q.push( s );
	while( !Q.empty() )
	{
		x = Q.front();
		Q.pop();
		for ( i = 0; i < v[ x ].size(); ++i )
		{
			if ( cost[ x ] + 1 < cost[ v[ x ][ i ] ] )
			{
				cost[ v[ x ][ i ] ] = cost[ x ] + 1;
				Q.push( v[ x ][ i ] );
			}
		}
	}
	for ( i = 1; i <= n; ++i )
		if ( cost[ i ] == N ) fout << -1 << ' ';
		else
			fout << cost[ i ] << ' ';
	fout << '\n';
	return 0;
}