#define _CRT_SECURE_NO_WARNINGS
#include <malloc.h>
#include <stdio.h>
#include <string.h>
#define NAME "bfs"
#define OPEN f = fopen(NAME".in","r");g = fopen(NAME".out","w");
FILE *f,*g;

#define NAMX 100000

struct _NOD;
typedef struct _NOD NOD;

struct _NOD
{
	int n;
	NOD *nx;
};
int distance [NAMX];
int vis[NAMX];
NOD *graph[NAMX];

int n,m,s,i,dis,x,y;
NOD *p,*q,*r,*l1,*l2;
int main()
{
	OPEN;
	fscanf(f,"%d %d %d",&n,&m,&s);
	s--;
	for(i=0;i<m;i++)
	{
		fscanf(f,"%d %d",&x,&y);
		x--;
		y--;
		q = (NOD *)malloc(sizeof(NOD));
		q->n = y;
		q->nx = graph[x];
		graph[x] = q;
	}
	for(i=0;i<n;i++)
		distance[i] = -1;
	distance[s] = 0;
	vis[s] = 1;
	q = (NOD *)malloc(sizeof(NOD));
	q->nx = NULL;
	q->n = s;
	l1 = q;
	l2 = NULL;
	dis = 0;
	while(l1)
	{
		dis++;
		for(p = l1;p;p=p->nx)
			for(q = graph[p->n];q;q=q->nx)
				if(!vis[q->n])
				{
					vis[q->n] = 1;
					distance[q->n] = dis;
					r = (NOD *)malloc(sizeof(NOD));
					r->n = q->n;
					r->nx = l2;
					l2 = r;
				}
		l1 = l2;
		l2 = NULL;
	}
	for(i=0;i<n;i++)
		fprintf(g,"%d ",distance[i]);

}