#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

#define maxN 100005
#define maxM 1000005

using namespace std;

FILE *f = fopen ("bfs.in","r");
FILE *g = fopen ("bfs.out","w");

int n, m, S, viz[maxN], dist[maxN];
int T[2][maxM], k, start[maxN], Q[maxN];

void read()
{
	fscanf (f, "%d%d%d", &n, &m, &S);
	while (m--)
	{
		int a, b;
		
		fscanf (f, "%d%d", &a, &b);
		k++;
		T[0][k] = b;
		T[1][k] = start[a];
		start[a] = k;
	}
	
	memset (dist, -1, sizeof(dist) );
}

void bf(int nod)
{
	int x, p, IncC = 0, SfC = 0;
	
	viz[nod] = 1;	dist[nod] = 0;
	Q[0] = nod;
	
	while ( IncC <= SfC )
	{
		x = Q[IncC++];
		
		p = start[x];
		while (p)
		{
			if ( !viz[ T[0][p] ] )
			{
				dist[ T[0][p] ] = dist[x] + 1;
				viz [ T[0][p] ] = 1;
				Q[++SfC] = T[0][p];
			}
			p = T[1][p];
		}
	}
}

int main()
{
	read();
	bf(S);
	
	for (int i = 1; i <= n; i++)
		fprintf (g, "%d ", dist[i]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}