#include<iostream>
#include<stdio.h>
#include<fstream>
using namespace std;
int n,m,s,viz[10000],a[10000][10000],c[100000],cost[10000];
int p,u;
void ActualizareCoada(void)
{
    for(int k=p;k<u;k++)
     c[k]=c[k+1];
    u--;
}

int parcurg(int i)
{
	viz[i]=1;
	int j;
	p=1;
	u=1;
	c[p]=i;
	while(p<=u)
	{
		for(j=1;j<=n;j++)
			{
				if((a[c[p]][j]==1)&&(viz[j]==0))
			{
				u++;
				viz[j]=1;
				c[u]=j;
			//	cost[j]=cost[j]+1;;
				//if(a[s][j]==0)
					cost[j]=cost[c[p]]+1;
			}

			}
		p++;ActualizareCoada();

	}
}



int main()
{
	ifstream f("bfs.in");
	f>>n>>m>>s;
	int i,j,k;
	for(i=1;i<=m;i++)
		{
			f>>j>>k;
			a[j][k]=1;
		}
	parcurg(s);
	ofstream g("bfs.out");
	for(i=1;i<=n;i++)
		{if((cost[i]==0)&&(i!=s))
			cost[i]=-1;
		g<<cost[i]<<" ";
		}
}