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

    {
        viz[i]=-1;
    }
    viz[s]=0;
    coada[1]=s;
    pr=1;
    ul=1;
    while(ul-pr+1>0)
    {
        v=coada[pr];
        for(p=l[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++)
    {
        fout<<viz[i]<<" ";
    }
    fout.close();
    fin.close();
    return 0;
}