#include <fstream>
using namespace std;
#define dim 10001
char mat[dim][dim];
int cost[dim];
char v[dim];
int coada[dim*dim][2];
int n, m, s;

void bfs(int nod)
{
	coada[1][0]=nod;
	
	int inc=1;
	int sf=1;
	
	while(inc<=sf)
	{
		for(int k=1;k<=n;++k)
		{
			if(v[k]==0 && mat[coada[inc][0]][k]==1)
			{
				if(k==coada[inc][0])
					cost[k]=0;
				else
				{
					if( (cost[k]>coada[inc][1]+1) || cost[k]==-1)
					{
						cost[k]=coada[inc][1]+1;
						v[k]=1;
						++sf;
						coada[sf][0]=k;
						coada[sf][1]=coada[inc][1]+1;
					}
				}
			}
		}
		++inc;
	}
	
}

int main()
{
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int i, a, b;
	
	fin>>n >>m >>s;
	
	for(i=1;i<=m;++i)
	{
		fin>>a >>b;
		mat[a][b]=1;
	}
	
	for(i=1;i<=n;++i)
		cost[i]=-1;
	cost[s]=0;
	bfs(s);
	
	for(i=1;i<=n;++i)
		fout<<cost[i] <<" ";
	return 0;
}