#include<fstream>
#include<queue>
#include<vector>
using namespace std;

void read();
void bfs();
void write();

int n, m, s;
vector<bool> selected(100005);
vector<vector<int> > mat(100005);
vector<int> road(100005);
queue<int> q;

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

void read()
{
	ifstream fin( "bfs.in" );
	fin >> n >> m >> s;
	for ( int i = 0; i < m; ++i )
	{
		int x, y;
		fin >> x >> y;
		mat[x].push_back(y);
	}
	fin.close();
}

void bfs() 
{
	q.push(s);
	int act = s;
	
	road[act] = 0;
	
	while ( !q.empty() )
	{
		act = q.front();
		selected[act] = true;
		for ( vector<int>::iterator i = mat[act].begin(); i < mat[act].end(); ++i )
			if ( !selected[*i] )
			{
				selected[*i] = true;
				road[*i] = road[act] + 1;
				q.push( *i );
			}
		q.pop();
	}
}

void write()
{
	ofstream fout( "bfs.out" );
	for ( int i = 1; i < 1 + n; ++i )
	{
		if ( selected[i] || i == s )
			fout << road[i] << ' ';
		else
			fout << -1 << ' ';
	}
	fout.close();
}