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

#define SIZE 100001


list<int> A[SIZE]; // Adjacency lists
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].push_back(y);
	}
	
	// Do BFS
	queue<pair<int, int> > Q;
	Q.push(make_pair(s, 0));
	V[s] = true;
	
	while (!Q.empty()) 
	{
		pair<int, int> p = Q.front();
		Q.pop();
		
		int node = p.first;
		MP[node] = p.second;
		
		
		for (list<int>::iterator it = A[node].begin(); it != A[node].end(); ++it)
		{
			if (!V[*it]) 
			{
				Q.push(make_pair(*it, p.second + 1));
				V[*it] = true;
			}	
		}
	}
	
	for (int i = 1; i < s; ++i) 
		ofs << (MP[i] > 0 ? MP[i] : -1) << " ";

	ofs << 0 << " ";
	
	for (int i = s+1; i <= n; ++i) 
		ofs << (MP[i] > 0 ? MP[i] : -1) << " ";

	return 0;
}