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

#define SIZE 100001

bool A[SIZE][SIZE]; // Adjacency matrix
bool V[SIZE]; // Visited vector
int MP[SIZE]; // Stores the size of the minimum path from START to DESTINATION

int main() 
{
	ifstream ifs("bfs.in");
	ofstream ofs("bfs.out");
	
	int n, m, s;
	
	ifs >> n >> m >> s;
	
	for (int i = 0; i < m; ++i)
	{
		int x, y;
		ifs >> x >> y;
		
		A[x][y] = true;
	}
	
	// Do BFS
	queue<pair<int, int>> Q;
	Q.enqueue(make_pair(s, 0));
	V[s] = true;

	while (!Q.empty()) 
	{
		pair<int, int> p = q.front();
		MP[p.first]  = p.second;
		
		for (int i = 1; i <= n; ++i) 
			if (A[node][i] && !V[i]) 
				Q.enqeue(make_pair(i, p.second));
	}
	
	for (int i = 1; i < s; ++i) 
		cout << MP[i] << " ";

	cout << MP[s] << " ";
	
	for (int i = s+1; i < n; ++i) 
		cout << MP[i] << " ";

	return 0;
}