#include <fstream>
using namespace std;
struct nod
{
    int vecin;
    nod *leg;
};
int n,m,coada[100001],viz[100001],s;
nod * LV[100001],*p;
ifstream f("bfs.in");
ofstream g("bfs.out");
int main ()
{
    int i,u,v,pr,ul;
    f>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        f>>u>>v;
        p = new nod;
        p->vecin =v;
        p->leg=LV[u];
        LV[u]=p;
    }
    for(i=1;i<=n;i++)
        viz[i]=-1;

    viz[s]=0;
    //BFS
    coada[1]=s;
    pr=1;
    ul=1;
    while(pr<=ul)
    {
        v=coada[pr];
        for(p=LV[v];p!=0;p=p->leg)
        {
            if(viz[p->vecin]==-1)
            {
                ul++;
                coada[ul]=p->vecin;
                viz[p->vecin]=1+viz[v];
            }
        }
        pr++;
    }
    for(i=1;i<=n;i++)
        g<<viz[i]<<" ";

    return 0;
}