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

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int n,m,s;
vector<int> G[100005];
int D[100005];

void read();
void solve();
void print();

int main()
{
	read();
	solve();
	print();
	return 0;
}

void read()
{
	int a,b;
	fin>>n>>m>>s;
	for(int i=0;i<m;i++)
	{
		fin>>a>>b;
		G[a].push_back(b);
	}
}

void solve()
{
	memset(D,-1,sizeof(D));
	bool InQueue[100005];
	memset(InQueue,false,sizeof(InQueue));
	queue<int> Q;
	Q.push(s);
	InQueue[s] = true;
	D[s] = 0;
	while(!Q.empty())
	{
		int nod = Q.front();
		Q.pop();
		for(unsigned int i = 0; i < G[nod].size(); i++)
		{
			if(!InQueue[G[nod][i]])
			{
				Q.push(G[nod][i]);
				InQueue[G[nod][i]] = true;
				D[G[nod][i]] = D[nod] + 1;
			}
		}
	}
}

void print()
{
	for(int i=1;i<=n;i++)
	{
		fout<<D[i]<<' ';
	}
}