#include <iostream>
#include <fstream>

using namespace std;

int prez[100001],v[100001],s,n,m,i,j,k;

fstream f,g;

struct nod
{
    int d;
    nod *urm;
}*con[100000],*u[100000];

int main()
{
    nod *N;
    f.open("bfs.in",ios_base::in);
    g.open("bfs.out",ios_base::out);
    f>>n>>m>>s;
    for(i=0;i<n;i++)
    {
        prez[i]=-1;
        con[i]=NULL;
    }
    for(i=0;i<m;i++)
    {
        f>>j>>k;
        N=new nod;
        j--;k--;
        if(con[j]==NULL)
        {
            con[j]=N;
            con[j]->urm=NULL;
            con[j]->d=k;
            u[j]=con[j];
        }
        else
        {
            u[j]->urm=N;
            N->urm=NULL;
            N->d=k;
            u[j]=N;
        }
    }
    prez[s-1]=0;
    v[0]=s-1;
    i=0;
    j=1;
    while(i!=j)
    {
        for(N=con[v[i]];N!=NULL;N=N->urm)if(prez[N->d]==-1)
        {
            prez[N->d]=prez[v[i]]+1;
            v[j]=N->d;
            j++;
        }
        i++;
    }
    for(i=0;i<n;i++)g<<prez[i]<<' ';
}