#include <cstdio>
using namespace std;
const int nd=100005;
struct nod{int val; nod *urm; }*p[nd];
int n,m,s,sol[nd],c[nd],lg[nd],viz[nd];
void read()
{ nod *aux;
  int x,y,i;
freopen("bfs.in","r",stdin); scanf("%d %d %d\n",&n,&m,&s);
for(i=1;i<=m;++i)
    {
    scanf("%d %d\n",&x,&y);
    aux=new nod; aux->val=y; aux->urm=p[x]; p[x]=aux;
    }
fclose(stdin);
}
void solve()
{ int pr,u,i;
  nod *aux;
pr=u=1; c[1]=s; lg[1]=0;
for(i=1;i<=n;++i)
    {
    sol[i]=-1;
    viz[i]=0;
    }
sol[s]=0; viz[s]=1;
while(pr<=u)
    {
    aux=p[c[pr]];
    while(aux!=NULL)
        {
        if(viz[aux->val]==0){
                            viz[aux->val]=1;
                            c[++u]=aux->val;
                            lg[u]=lg[pr]+1;
                            sol[aux->val]=lg[u];
                            }
        aux=aux->urm;
        }
    ++pr;
    }
}
void write()
{ int i;
freopen("bfs.out","w",stdout);
for(i=1;i<=n;++i)
    printf("%d ",sol[i]);
fclose(stdout);
}
int main()
{
read();
solve();
write();
return 0;
}