#include <stdio.h>

using namespace std;

#define maxn 100010

int n,m,s;
int a[maxn];
int v[2][maxn];

void BFS(int nod)
{
	int i,b,j;
    for (i=1; i<=n; i++) a[i]=-1;
    a[nod]=0; b=1;
	while (b)
	{
	    b=0;
        for (i=1; i<=m; i++)
           if (a[v[1][i]]!=-1  && ( a[v[2][i]]==-1 || a[v[2][i]] > a[v[1][i]]+1 ))
              {
                  a[v[2][i]]=a[v[1][i]]+1;
                  b=1;
              }
    }
}

int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	int i;
    scanf("%i%i%i",&n,&m,&s);
    for (i=1; i<=m; i++)  scanf("%i%i",&v[1][i],&v[2][i]);
    BFS(s);
    for (i=1; i<=n; i++)  printf("%i ",a[i]);
    return 0;
}