#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<long> vec[100001];
long m,n,s,lungime;
long sol[100001],vecini[100001],a[100001];
void bfs(long nod)
{ 
	for(long i=1;i<=n;i++)
		sol[i]=-1;
    sol[nod]=0;
	lungime=1;
	a[lungime]=nod;
	for(long i=1;i<=lungime;i++)
		for(long j=0;j<vecini[a[i]];j++)
			if(sol[vec[a[i]][j]]==-1)
			{
				a[++lungime]=vec[a[i]][j];
				sol[a[lungime]]=sol[a[i]]+1;
			}
}
int main()
{
	FILE *f;
	FILE *g;
	f=fopen("bfs.in", "rt");
	g=fopen("bfs.out", "wt");
	fscanf(f,"%d %d %d", &n, &m, &s);
	  for(long i=0;i<m;i++)
	  {
		int x,y;
		fscanf(f,"%d %d", &x, &y);
		vec[x].push_back(y);
	  }
	  for(long i=1;i<=n;i++)
		  vecini[i]=vec[i].size();
	bfs(s);
	for(long i=1;i<=n;i++)
		fprintf(g,"%d ",sol[i]);
	for(int i=0;i<=n;i++)
		printf("%d",a[i]);
	fclose(f);
	fclose(g);
	return 0;
}