#include<fstream>
#include<queue>
#include<vector>

using namespace std;
int *distanta;
int *vizitat;

void BFS(vector<int> *adj, int s)
{
	queue<int> q;
	int v, i;
	q.push(s);
	vizitat[s] = 1;
	while(!q.empty())
	{
		v = q.front();
		q.pop();
		for(i = 0; i < (int)adj[v].size(); i++)
		{
			if(vizitat[adj[v][i]] == 0)
			{
				vizitat[adj[v][i]] = 1;
				distanta[adj[v][i]] = distanta[v] + 1;
				q.push(adj[v][i]);
			}
		}
	}
}

int main()
{
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	vector<int> *adj;
	// n = noduri, m = muchii, s = start, i = contor, u, v = pt citirea muchiilor
	int n, m, s, i, u, v; 
	fin >> n >> m >> s;
	adj = new vector<int>[n];
	for(i = 0; i < m; i++)
	{
		fin >> u >> v;
		adj[u - 1].push_back(v - 1);
	}
	s--; // retinem nodurile de la 0 la n-1
	distanta = new int[n];
	vizitat = new int[n];
	for(i = 0; i < n; i++)
	{
		distanta[i] = -1;
		vizitat[i] = 0;
	}
	distanta[s] = 0;
	BFS(adj, s);
	for(i = 0; i < n; i++)
		fout << distanta[i] << " ";
	return 0;
}