#include <fstream>
using namespace std;

ifstream F("bfs.in");
ofstream G("bfs.out");

#define Nmax 7511
#define Mmax 15011

int Leg[Mmax*2];
int Beg[Nmax],End[Nmax];
int x[Mmax],y[Mmax];

int Nbr[Nmax];
int Act[Nmax];

int N,M;

int Lung[Nmax];

int Coada[Nmax],Co;
int Coada2[Nmax],Co2;

void BF(int Start,int Step,int Stop)
{
	Coada[++Co]=Start;
	Lung[Coada[1]]=Step;
	
	for (; !Lung[Stop] ; ++ Step )
	{
		for (int i=1;i<=Co;++i)
			for (int j=Beg[Coada[i]];j<=End[Coada[i]];++j)
			{
				if ( !Lung[Leg[j]] )
				{
					Lung[Leg[j]]=Step+1;
					Coada2[++Co2]=Leg[j];
				}
				if ( Lung[Stop] ) return;
			}
		for (int i=1;i<=Co2;++i)
			Coada[i]=Coada2[i];
		Co=Co2;
		Co2=0;
		
		if ( Co==0 ) return;
	}
}

int main()
{
	int X;
	F>>N>>M>>X;
	int Y=N+1;
	
	for (int i=1;i<=M;++i)
	{
		F>>x[i]>>y[i];
		++Nbr[x[i]];
	}

	Beg[1]=1;
	Act[1]=1;
	End[1]=Nbr[1];
	
	for (int i=2;i<=N;++i)
	{
		Beg[i]=End[i-1]+1;
		Act[i]=Beg[i];
		End[i]=Beg[i]+Nbr[i]-1;
	}
	
	for (int i=1;i<=M;++i)
		Leg[ Act[x[i]]++ ]=y[i];
	
	BF(X,1,Y);
	
	for (int i=1;i<=N;++i)
		if (Lung[i]==0)
			G<<"-1 ";
		else
			G<<Lung[i]-1<<' ';
}