#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int nodes;
int source;
vector< vector<int > > List;

void read(const char * buff_file)
{
	fstream f(buff_file, ios::in);
	f>>nodes;
	int edges;
	f>>edges;
	f>>source;

	List.reserve(nodes+1);
	List.resize(nodes+1);
	
	int left, right;
	for (int i=1; i<=edges; ++i)
	{
		f>>left>>right;
		List[left].push_back(right);
	}
};

int dist[100005];
int v[100005];
int nr_v;
bool used[100005];

void solve()
{
	for (int i=1; i<=nodes; ++i)
		dist[i]=-1;
	dist[source]=0;
	used[source]=1;
	nr_v=0;
	v[++nr_v]=source;
	
	for (int i=1; i<=nr_v; ++i)
	{
		for (vector<int>::iterator it=List[v[i]].begin(); it < List[v[i]].end(); it++)
			if (used[*it]==0)
			{
				used[*it]=1;
				dist[*it]=1+dist[v[i]];
				v[++nr_v]=*it;
			}
	}
};

void print(const char * out_file)
{
	fstream g(out_file, ios::out);
	for (int i=1; i<=nodes; ++i)
		g<<dist[i]<<" ";
}

int main()
{
	read("bfs.in");
	solve();
	print("bfs.out");
	return 0;
}