#include<iostream>
#include<fstream>

using namespace std;
int n,m,i,x,s,y,q[1000000];
int viz[1000000];
int pq,nq;

struct nod
{
    int val;
    nod *next;
};
nod *l[1000000];

void bf(int s)
{int x; nod *p;
    for(i=1;i<=n;i++)
    {
        viz[i]=-1;
        q[i]=0;
    }
    pq=nq=1;
    q[pq]=s;
    viz[s]=0;
    while (pq<=nq)
    {
        x=q[pq];
        p=l[x];
        while(p)
            {if(viz[p->val]==-1)
        {
            q[++nq]=p->val;
            viz[p->val]=viz[x]+1;

        }
        p=p->next;
        }
   pq++;
}
}

int main()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    nod *p;
    f>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        p=new nod;
        p->val=y;
        p->next=l[x];
        l[x]=p;
    }
    bf(s);
    for(i=1;i<=n;i++)
        g<<viz[i]<<" ";
}