#include <stdio.h>
#include <bitset>
#include <deque>

using namespace std;
FILE *f,*g;
int start[1000002],t[3][2000004];
bitset <1000002>viz;
int drum[1000002];
deque <int> q;

int main()
{
    int x,i,j,m,n,o,k=0,nod,ss,no;
    f=fopen("bfs.in","r");
    g=fopen("bfs.out","w");
    fscanf(f,"%d %d %d",&n,&m,&x);
    for(o=1;o<=m;++o)
    {
        fscanf(f,"%d %d",&i,&j);
        ++k;
        t[0][k]=j;
        t[1][k]=start[i];
        start[i]=k;
    }
    for(i=1;i<=n;++i)
        drum[i]=2000000000;
    q.push_back(x);///introduc nodul de la care pornesc in coada
    viz[x]=1;///am vizitat acel nod
    drum[x]=0;///distanta pana acum e 0
    while(!q.empty())
    {
        nod=q.front();///noul nod din coada
        q.pop_front();///eliminam nodul
        no=start[nod];
        ss=drum[nod];///distanta pana la nodul nod
        while(no)///parcurg toti vecinii nodului nod
        {
            if(viz[t[0][no]]==0 && ss+1<drum[t[0][no]])///daca nu am mai trecut prin acel nod vecin sau daca am gasit o distanta mai mica pana la acela
            {
                q.push_back(t[0][no]);///introduc noul nod in coada
                drum[t[0][no]]=ss+1;///noua distanta
                viz[t[0][no]]=1;///marchez acel vecin ca vizitat
            }
            no=t[1][no];
        }
    }
    for(i=1;i<=n;++i)
    {
        if(drum[i]!=2000000000)
            fprintf(g,"%d ",drum[i]);
        else
            fprintf(g,"-1 ");
    }


    fclose(f);
    fclose(g);
    return 0;
}