#include<stdio.h>
#include<vector>
#define nmax 100010

using namespace std;

int n,m,x,i,j,cost[nmax],v1,v2,coada[nmax],first, last;
vector<vector<int> > a(nmax);

void bfs()
{
	first=1;
	last=1;
	coada[1]=x;
	for(i=1;first<=last;i++)

	{		for(j=0;j<a[coada[i]].size();j++)
			if(cost[a[coada[i]][j]]==-1||cost[a[coada[i]][j]]>cost[coada[i]]+1)
			{
				coada[++last]=a[coada[i]][j];
				cost[a[coada[i]][j]]=cost[coada[i]]+1;
			}
	first++;
	}
}


int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	scanf("%d %d %d", &n, &m, &x);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d", &v1, &v2);
		a[v1].push_back(v2);
		cost[i]=-1;
	}
	cost[x]=0;
	bfs();
	for(i=1;i<=n;i++)
		printf("%d ", cost[i]);
	printf("\n"); 
	return 0;
}