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

using namespace std;

#define NMAX 100005

int N, M, S;
vector<int> neigh[NMAX];
int d[NMAX];
bool inQ[NMAX];

int main()
{	
	ifstream in("bfs.in");
	ofstream out("bfs.out");
	
	in >> N >> M >> S;
	
	for(int i = 0; i < M; ++i)
	{
		int a, b;
		in >> a >> b;
		neigh[a].push_back(b);
	}
	
	for(int i = 1; i <= N; ++i)
		d[i] = -1;
	
	d[S] = 0;
	
	queue<int> Q;
	
	Q.push(S);
	inQ[S] = true;
	
	while(!Q.empty())
	{
		int p = Q.front();
		Q.pop();
		
		for(unsigned i = 0; i < neigh[p].size(); ++i)
		{
			int f = neigh[p][i];
			if(!inQ[f])
			{	
				d[f] = d[p] + 1;
				Q.push(f);
				inQ[f] = true;
			}
		}
	}
	
	for(int i = 1; i <= N; ++i)
		out << d[i] << " "; 
	
	return 0;
}