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

#define SIZE 100001

typedef struct ListNode 
{
	int val;
	ListNode* next;
} ListNode;

ListNode* add_front(ListNode* head, int val) 
{
	ListNode* node = new ListNode;
	node->val = val;
	node->next = 00;
	
	if (head == 00) 
	{
		return node;
	} 
	else 
	{
		node->next = head;
	}
	
	return node;
}

ListNode* 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] = add_front(A[x], y);
	}
	
	// Do BFS
	queue<pair<int, int> > Q;
	Q.push(make_pair(s, 0));

	while (!Q.empty()) 
	{
		pair<int, int> p = Q.front();
		Q.pop();
		
		V[p.first] = true;
		MP[p.first] = p.second;
		
		ListNode* it = A[p.first];
		while (it != 00)
		{
			if (!V[it->val]) 
				Q.push(make_pair(it->val, p.second + 1));
				
			it = it->next;	
		}
	}
	
	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;
}