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

using namespace std;

const int Nmax = 100010;

int N,M,S;
vector<int> L[Nmax];
int sol[Nmax];

void solve()
{
	int current;
	queue< int > q; 
	vector<int>::iterator it;

	sol[S] = 1;
	q.push(S);

	while (!q.empty())
	{
		current = q.front();
		q.pop();

		it = L[current].begin();
		for(; it != L[current].end() ; ++it)
			if (!sol[ (*it) ])
			{
				sol[ (*it) ] = sol[ current ] + 1;
				q.push( (*it) );
			}
	}
}

void read()
{
	int a,b;
	ifstream fin;
	fin.open("bfs.in");
	fin >> N;
	fin >> M;
	fin >> S;

	for(int i=0; i<M ; ++i)
	{
		fin >> a;
		fin >> b;
		L[a].push_back(b);
	}

	fin.close();
}

void print()
{
	fstream fout;
	fout.open("bfs.out");
	for(int i=1;i<=N;++i)
		fout << sol[i]-1 << " ";
	fout.close();
}

int main()
{
	read();
	solve();
	print();

	return 0;
}