#include <fstream>
#include <iostream>

using namespace std;
const int Nmax=100001;
const int Mmax=1000000;
unsigned short mat[Nmax][Nmax/16];

int n,m,ns,pi,ps;
int coada[Mmax],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;
}

unsigned short 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];
    return(masca>0);
}
void bfs(int ns)
{
    int i;
    pi=1;
    ps=1;
    coada[1]=ns;
    setmat(0,ns);
    while(pi<=ps)
    {
        for(i=1;i<=n;i++)
            if(getmat(0,i)==0)
                if(getmat(coada[pi],i))
                {
                    ps++;
                    coada[ps]=i;
                    setmat(0,i);
                    dist[i]=dist[coada[pi]]+1;
                }
        pi++;
    }
}

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