#include<iostream>
#include<fstream>

#define IMAX 1000000

using namespace std;


int n,i,j,m,S;
int *a[IMAX];
int culoare[IMAX],cost[IMAX],coada[IMAX],nc,prim;
//int drum[IMAX];

ifstream f ("bfs.in");
ofstream o ("bfs.out");

void citire()
{
    int x,y;
    f>>n>>m>>S;
    for(i=1;i<=n;i++)
        {
            a[i]=(int*)realloc(a[i],sizeof(int));
            a[i][0]=0;
            cost[i]=-1;
        }
    for(i=1;i<=m;i++)
        {
         f>>x>>y;
        a[x][0]++;
        a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
        a[x][a[x][0]]=y;
        }

}

void afis()
{
    for(i=1;i<=n;i++)
        {for(j=1;j<=a[i][0];j++)
            cout<<a[i][j]<<" ";
        cout<<"\n";}
}



void parc_latime(int x)
{
 //0- alb
 //1- gri
 //2- negru
prim=nc=0;
cost[x]=0;
coada[prim]=x;
 culoare[x]=1;
while(prim<=nc)
 {
   x=coada[prim++];
 for(i=1;i<=a[x][0];i++)
        if(culoare[a[x][i]]==0)
            {
                coada[++nc]=a[x][i];
                culoare[a[x][i]]=1;
               // drum[a[x][i]]=x;
                cost[a[x][i]]=cost[x]+1;

            }
    culoare[x]=2;

    //prim++;

    }


}

int main()
{
citire();


parc_latime(S);
for(i=1;i<=n;i++)
    o<<cost[i]<<" ";




return 0;}