#include <fstream>
using namespace std;
const int Nmax=100001;
const int Mmax=1000000;
unsigned short mat[Nmax][Nmax/16];
int n,m,pi,ps,ns,coada[Nmax],dist[Nmax];
int getmat(int a,int b)
{
    unsigned short col,bit,masca=32768;
    col=b/16;
    bit=b%16;
    masca=masca>>bit;
    masca=masca & mat[a][col];
    if(masca>0) return 1;
    else return 0;
}
void setmat(int a, int b)
{ unsigned short col,bit,masca=32768;
        col=b/16;
        bit=b%16;
        masca=masca>>bit;
        mat[a][col]=mat[a][col] | masca;
}
void BFS(int ns)
{ int i;
    pi=1;ps=1;
    coada[pi]=ns;
    setmat(0,ns);
    while(pi<=ps)
    {for(i=1;i<=n;i++)
        if(getmat(0,i)==0)
            if(getmat(coada[pi],i)==1)
            { ps++;
                coada[ps]=i;
                setmat(0,i);
                dist[i]=dist[coada[pi]]+1;
            }pi++;

    }

}

int main()
{
    int i,a,b;
    ifstream in("bfs.in");
    ofstream out("bfs.out");
    in>>n>>m>>ns;
    for(i=1;i<=m;i++)
    {   in>>a>>b;
        setmat(a,b);}
    BFS(ns);
    for(i=1;i<=n;i++)
        if(dist[i]==0)dist[i]=-1;
        dist[ns]=0;
        for(i=1;i<=n;i++)
        out<<dist[i]<<" ";
    return 0;
}