#include <fstream>

using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

int n,m,i,j,ma[2500][2500],s,x,y,viz[100005],pr,ul,d[100005],vf,cost;
struct cd
{
    int nd,ct;
};
cd coada[100004];

int main()
{
    fin>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        ma[x][y]=1;
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=-1;
    }
    ul++;
    pr++;
    coada[ul]={s,0};

    for(i=1;i<=n;i++)
        d[i]=-1;
    d[s]=0;
    viz[s]=1;

    while(pr<=ul)
    {
        vf=coada[pr].nd;
        cost=coada[pr].ct;
        for(i=1;i<=n;i++)
            if(ma[vf][i]==1 && viz[i]==-1)
            {
                d[i]=d[vf]+1;
                ul++;
                viz[i]=1;
                coada[ul]={i,cost+1};
            }
        pr++;
    }
    for(i=1;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
    return 0;
}