#include <iostream>
#include <fstream>
using namespace std;
int viz[100000],c[100000],d[100000],prim,ultim,nr;
struct nod
{
    int info;
    nod *next;
}*l[100000];
void bfs()
{
    nr++;
    nod *p;
    if(prim<=ultim)
    {for(p=l[c[prim]];p!=NULL;p=p->next)
        if(viz[p->info]==0) {c[++ultim]=p->info;
        viz[p->info]=1;
        d[p->info]=nr;}
   prim++;
     bfs();
       }
}
int main()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    nod *p;
    int i,x,y,n,m,s;
    f>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        p=new nod;
        p->info=y;
        p->next=l[x];
        l[x]=p;
    }
    viz[s]=1;
    prim=1;
    ultim=1;
    c[prim]=s;
    bfs();
    for(i=1;i<=n;i++)
       if(d[i]==0) d[i]=-1;
    d[s]=0;
    for(i=1;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}