#include <fstream>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
const int Nmax=100001;
const int Mmax=1000000;
unsigned short mat[Nmax][Nmax/16];
int n,m,pi,ps,ns,coada[Nmax],dist[Nmax];
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;

}
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 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;
    in>>n>>m>>ns;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        setmat(a,b);
    }
    in.close();
//    out<<getmat(5,3);

    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]<<" ";
    out.close();

    return 0;
}