#include<fstream>
#define NMAX 100010
using namespace std;
typedef struct lista* nod;
struct lista
{
    int Key;
    nod Next;
};
typedef nod Adiac[NMAX];
Adiac V,U;
int viz[NMAX],k,drum[NMAX];
ifstream f ("bfs.in");
ofstream g ("bfs.out");

void BFS(int K, int i)
{
     if(!viz[V[K]->Key])
     {
     viz[K]=1;           
     nod x;
     for(x=V[K];x;x=x->Next) viz[x->Key]=1,drum[x->Key]=i;
     for(x=V[K];x;x=x->Next) BFS(x->Key,i+1);  
     }
}

int main()
{
    int n,m,s,i,x,y;
    f>>n>>m>>s;
    for(i=1;i<=n;i++) V[i]=NULL;
    for(i=0;i<m;i++)
    {
       f>>x>>y;
       nod L;
       if(!V[x])
       {
          V[x]= new lista;   
          V[x]->Key=y;
          V[x]->Next=NULL;
          U[x]=V[x];
       }
       else
       {
           nod L = new lista;
           L->Key=y;
           L->Next=NULL;
           U[x]->Next=L;
           U[x]=L;
       }
    } 
    BFS(s,1);
    drum[s]=0;
    for(i=1;i<=n;i++)
    {
        if(!viz[i]) drum[i]=-1;
        g<<drum[i]<<" ";           
    } 
    f.close();
    g.close();
    return 0;
}