#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

#define Nmax 100000
#define Mmax 1000000

vector <int> lista[Nmax];

int n,m,vizitat[Nmax],p,u,coada[Nmax],Start;

void creare(char *g)
{ifstream f(g);
f>>n;
f>>m;
f>>Start;
int i,x,y;
for (i=1;i<=m;i++)
	{f>>x;
	 f>>y;
	 lista[x].push_back(y);}}

void initializare(int i)
{p=u=1;
vizitat[i]=0;
coada[u]=i;}

void adauga(int i,int k)
{u++;
vizitat[i]=vizitat[k]+1;
coada[u]=i;}

void elimina()
{p++;}

void prelucrare()
{int k=coada[p];
for(unsigned int i=0;i<lista[k].size();i++) if (vizitat[lista[k][i]]==-1) adauga(lista[k][i],k);
elimina();}

void bf(int k)
{initializare(k);
while (p<=u) prelucrare();}

void init()
{for(int i=1;i<=n;i++)
	vizitat[i]=-1;}

int main()
{creare("bfs.in");
init();
bf(Start);
ofstream g("bfs.out");
for(int i=1;i<=n;i++)
	g<<vizitat[i]<<" ";
return 0;
}