#include <iostream>
#include <fstream>

using namespace std;

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

int START[100002], T[2][1000002], viz[100002], d[100002], n, s;

void BFS(int vf)
{
    int coada[100002], pr, ul, i, x, y;
    coada[1]=vf;
    pr=1;ul=1;
    viz[vf]=1;
    while(pr<=ul)
    {
        x=coada[pr];
        for(i=START[x];i!=-1;i=T[1][i])
        {
            y=T[0][i];
            if(viz[y]==0)
            {
                viz[y]=1;
                ul++;
                coada[ul]=y;
                d[y]=d[x]+1;
            }
        }
        pr++;
    }
}

int main()
{
    int m,i,x,y,k;
    fin>>n>>m>>s;
    for(i=1;i<=n;i++)
        {START[i]=-1;d[i]=-1;}
    k=0;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        k++;
        T[0][k]=y;
        T[1][k]=START[x];
        START[x]=k;
    }
    d[s]=0;
    BFS(s);
    for(i=1;i<=n;i++)
        fout<<d[i]<<" ";

    fin.close();
    fout.close();

    return 0;
}