#include<fstream>
using namespace std;
struct nod
{
    int x;
    nod *leg;
};
nod *first,*last,*p,*q,*v[100001];
int d[100001],n,m,i,x,s,y;
int main()
{
     ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    fin>>n>>m>>s;
    for(i=1;i<=n;i++)
    {
        d[i]=-1;
        v[i]=0;
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        p=new nod;
        p->x=y;
        p->leg=v[x];
        v[x]=p;
    }
    first=new nod;
    first->x=s;
    first->leg=0;
    last=first;
    d[s]=0;
    while(first!=0)
    {
        x=first->x;
        for(p=v[x];p!=0;p=p->leg)
        {
            if(d[p->x]==-1)
            {
                d[p->x]=d[x]+1;
                q=new nod;
                q->x=p->x;
                q->leg=0;
                last->leg=q;
                last=q;
            }
        }
        p=first;
        first=first->leg;
        delete p;
    }
    for(i=1;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
    fout.close();
    fin.close();
    return 0;
}