#include <iostream>
#include <fstream>
#include <cstdio>
#define nm 100001
using namespace std;
ofstream g("bfs.out");
int n,m,s,coada[2][600000],t,i,x,y,p,u;
unsigned a[5001][5001],ap[100001];
int main()
{
    freopen("bfs.in","r",stdin);
    scanf("%d%d%d",&n,&m,&t);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    p=u=1;
    coada[0][1]=t;
    coada[1][1]=0;
    ap[t]=1;
    while(p<=u)
    {
        for(i=1;i<=n;i++)
        {
            if(a[coada[0][p]][i]==1&&ap[i]==0)
            {
                ap[i]=1;
                coada[0][++u]=i;
                coada[1][u]=coada[1][p]+1;
            }
        }
        p++;
    }
    for(i=1;i<=n;i++)
    {
        ap[coada[0][i]]=coada[1][i];
    }
    for(i=1;i<=n;i++)
    {
        if(ap[i]==0&&i!=t) g<<-1<<' ';
        else g<<ap[i]<<' ';
    }
    return 0;
}