#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
vector<int> dist;
vector<vector<int> > adj;
queue<int> Q;
void bfs()
{	
	while  (!Q.empty()){
		int s = Q.front();
		Q.pop();
		for (vector<int>::iterator it = adj[s].begin();it!=adj[s].end();it++)
		{
			int k =*it;
			if (dist[k]==-1){
				dist[k] =dist[s]+1;
				Q.push(k);
			}
		}
	}
}
int main()
{
	FILE *f = fopen("bfs.in","r");	
	FILE *g = fopen("bfs.out","w+");
	int n,m,s;
	fscanf(f,"%d %d %d",&n, &m,&s);
	adj.resize(n+1);
	for (int i=0;i<m;i++)
	{
		int a,b;
		fscanf(f,"%d %d",&a,&b);
		adj[a].push_back(b);
		//adj[b].push_back(a);
	}
	dist.resize(n+1);
	for (int i=0;i<=n;i++)
		dist[i]=-1;
	dist[s] =0;
	Q.push(s);
	bfs();
	for (int i=1;i<=n;i++)
		fprintf(g,"%d ",dist[i]);
	fclose(f);
	fclose(g);
}