#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

vector <int> Vecini[100005];
int Cost[100005];
int N,M,Start;
int Coada[100005],Lg;
int NrVecini[100005];

void Citire_si_formare()
{
    int x,y;
    scanf("%d %d %d",&N,&M,&Start);
    for(int i=1;i<=M;++i)
    {
        scanf("%d %d",&x,&y);
        Vecini[x].push_back(y);
    }
    for(int i=1;i<=M;++i)
        NrVecini[i]=Vecini[i].size();
}

void BFS()
{
    Coada[Lg++]=Start;
    Cost[Start]=0;
    for(int i=0;i<Lg;++i)
        for(int j=0;j<NrVecini[Coada[i]];++j)
            if(Cost[Vecini[Coada[i]][j]]==-1)
            {
                Coada[Lg++]=Vecini[Coada[i]][j];
                Cost[Vecini[Coada[i]][j]]=Cost[Coada[i]]+1;
            }

}



int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    Citire_si_formare();
    memset(Cost,-1,sizeof(Cost));
    BFS();
    for(int i=1;i<=N;++i)
        printf("%d ",Cost[i]);
    return 0;
}