#include <fstream>
using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

struct nod{int x;nod *urm;};
nod *p=NULL,*u=NULL;

int n,m,i,a,b,x;
nod *lstp[100001],*lstu[100001];

int cd[100001],v[100001],q1,q2,c[100001];

void add(int inf,nod *&prim,nod *&ult)
{
    nod *tmp;
    tmp=new nod;
    tmp->x=inf;
    if(prim==NULL) prim=tmp;
    else ult->urm=tmp;
    ult=tmp;
    ult->urm=NULL;
}

void bf(int s)
{
    q1=q2=1;
    cd[q1]=s;
    c[q1]=0;
    v[cd[q1]]=1;
    nod *j;
    while(q1<=q2)
    {
        for(j=lstp[cd[q1]];j;j=j->urm) if(v[j->x]==0) {v[j->x]=1;cd[++q2]=j->x;c[cd[q2]]=c[cd[q1]]+1;}
        q1++;
    }
}

int main()
{
    f>>n>>m>>x;

    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        add(b,lstp[a],lstu[a]);
    }

    bf(x);

    for(i=1;i<=n;i++) if(v[i]==0) g<<"-1 "; else g<<c[i]<<" ";
    g<<"\n";

    f.close();
    g.close();
    return 0;
}