#include <fstream>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n,m,x,y,i,k,j,s,pr,ul;
int start[100002],viz[100002],d[100002],coada[100002];
struct item
{
    int vecin,urm;
};
item L[1000002];
int main()
{
    fin>>n>>m>>s;
    for(i=1;i<=n;i++)
    {
        start[i]=0;///i in acest moment are lista vida de vecini
        d[i]=-1;
        viz[i]=0;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        ///start[x] este in acest moment pozitia in L[] a primului vecin al lui x la care avem acces
        k++;///pozitie noua in L[]
        L[k].vecin=y;
        ///y va fi adaugat in fata listei de vecini ai lui x
        L[k].urm=start[x];
        start[x]=k;///se pastreaza pozitia noului vecin in L[]
    }
    ///pentru fiecare varf i, ii vom afisa lista de vecini
    d[s]=0;
    coada[1]=s;
    pr=1;
    ul=1;
    viz[s]=1;
    while(pr<=ul)
    {
        x=coada[pr];
        for(i=start[x];i!=0;i=L[i].urm)
        {
            y=L[i].vecin;
            if(viz[y]==0)
            {
                d[y]=d[x]+1;
                ul++;
                coada[ul]=y;
                viz[y]=1;
            }
        }
        pr++;
    }
    for(i=1;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}