#include<iostream>
#include<fstream>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");

int A[2000][2000],n,m,S[2000],d[2000],start;
int c[2000],li=1,ls=0;

int coadavida()
{
	return li>ls;
}

void pune(int x)
{
	ls++;
	c[ls]=x;
}

int  extragere()
{
	int x=c[li];
	li++;
	return x;
}

void BF(int start)
{
	S[start]=1;
	pune(start);
	while(!coadavida())
	{
		int x=extragere();
		for(int i=1;i<=n;i++)
			if(A[x][i] && !S[i])
			{
				S[i]=1;
				d[i]=d[x]+1;
				pune(i);
			}
	}
}

void citire()
{
	in>>n>>m>>start;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		in>>x>>y;
		A[x][y]=1;
	}
}

int main()
{
	citire();
	BF(start);
	for(int i=1;i<=n;i++)
		if(d[i]==0 && i!=start)
			d[i]=-1;
	for(int i=1;i<=n;i++)
		out<<d[i]<<" ";
	return 0;
}