#include<cstdio>
using namespace std;
FILE *fin=fopen("bfs.in","r");
FILE *fout=fopen("bfs.out","w");
struct {int val,pas;}cd[1000001];
typedef struct nod{int val;
			       nod *next;};
nod *v[100001],*q;
int main()
{int vector[100001],i,n,m,k,a,b;
    fscanf(fin,"%d %d %d",&n,&m,&k);
    for (i=1;i<=n;++i)
		vector[i] = -1;
	vector[k] = 0;
    for (i=1;i<=m;++i)
	{   fscanf(fin,"%d %d",&a,&b);
	    if (a != b)
		{   q = new nod;
		    q -> next = v[a];
		    q -> val = b;
		    v[a] = q;
		}
	}
	cd[1].val = k;
	cd[1].pas = 0;
	int ic=0,sc=1;
	while (ic<=sc)
	{   ++ic;
		q = v[cd[ic].val];
	    while (q)
		{   if (vector[q->val] == -1)
		    {   ++sc;
				cd[sc].val = q->val;
				cd[sc].pas = cd[ic].pas+1;
				vector[q->val] = cd[sc].pas;
			}
			q = q->next;
		}
	}
	for (i=1;i<=n;++i)
		fprintf(fout,"%d ",vector[i]);
	fprintf(fout,"\n");
	fclose(fin);
	fclose(fout);
	return 0;
}