#include <iostream>
#include <fstream>
#define Dmax 100001
using namespace std;

fstream fin("bfs.in",ios::in);
fstream fout("bfs.out",ios::out);

long long n,m,s,C[Dmax],viz[Dmax],lv[10001][10001],timp[Dmax];

void citire()
{
    int i,x,y;
    fin>>n>>m>>s;
    for(i=1;i<=n;i++)
    {
        lv[i][0]=1;
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        lv[x][lv[x][0]]=y; lv[x][0]++;
    }

}

void afisare_lv()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        cout<<i<<": ";
        for(j=1;j<=n;j++)
        {
            cout<<lv[i][j]<<" ";
        }
        cout<<'\n';
    }
}

void parcurgere_BFS()
{
    int v,x,i,j,p,u,k;
    for(i=1;i<=n;i++)
    {
        timp[i]=-1;
    }

    k=0;
    p=1; u=1;
    C[p]=s; viz[s]=1; timp[s]=k;
    k++;
    while(p<=u)
    {
        v=C[p]; p++;

        for(i=1;i<=lv[v][0];i++)
        {
            if(viz[lv[v][i]]==0)
            {
                timp[lv[v][i]]=k;
                u++;
                C[u]=lv[v][i];
                viz[lv[v][i]]=1;
            }
        }
        if(viz[p]==0){k++;}

    }
    /*cout<<'\n';
    for(i=1;i<=n;i++)
    {
        cout<<viz[i]<<" ";
    }
    cout<<'\n';
    for(i=1;i<=u;i++)
    {
        cout<<C[i]<<" ";
    }
    cout<<'\n';*/
    for(i=1;i<=n;i++)
    {
        fout<<timp[i]<<" ";
    }

}

int main()
{
    citire();
    //afisare_lv();
    parcurgere_BFS();
}