/*
GRAF ORIENTAT GENIALA METODA

   Cerinta: Fiind dat un nod S, sa se determine, pentru fiecare nod X, numarul minim de
   arce ce trebuie parcurse pentru a ajunge din nodul sursa S la nodul X.
   In succesiunea de arce afisate pe pozitia S se va afisa valoarea 0, iar
   daca nu se gasete drum de la S la x se va afisa -1;

   OBSERVATIE:
     Se poate folosi pt memorarea acestui graf liste in liste
   deoarece singurele operatii care se realizeaza sunt de vizitare
   si inspectare a nodului.
*/
#include<iostream>
#include<fstream>

using namespace std;

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

typedef struct lista
        {
        int a;
        lista *next;
        }nod;

nod *L[100010];  //e o lista in lista  Notez cu L

int s,n,r,End,m,i,j,b[100010],c[1000010];

void parcurg()
        {

        nod *q;
        while(r<=End)
                {
                q=L[c[r]];
                while(q!=NULL)
                        {
                        if(b[q->a]==0 && q->a!=s)
                            {
                            End++;
                            c[End]=q->a;
                            b[c[End]]=b[c[r]]+1;

                            }
                        q=q->next;
                        }
                r++;
                }
        }


int main()
{
f>>n>>m>>s;

while(m>0)
        {
        f>>i>>j;
        nod *q;
        q=new nod;
        q->a=j;
        q->next=L[i];
        L[i]=q;
        m--;
        }
f.close();

/*  AFISARE ARCE
for (i=1; i<=n; i++)
    {
        cout<<i<<" :  ";
        nod *q;
        q=new nod;
        q=L[i];
        while (q != NULL)
        {
            cout<<q->a<<", ";
            q=q->next;
        }
        cout<<"\n";
    }
*/

End=r=1;
c[r]=s;  //c e un vector auxiliar

parcurg();

/* PROVENIENTA VECTORULUI c    {componenta conexa formata} vector de marcaje
for (i=1; i<=n; i++)
     cout<<c[i]<<" ";
*/



for(i=1;i<=n;i++)
                if(i==s)
                         g<<0<<' ';
                else
                  if(b[i]==0)
                               g<<-1<<' ';
                  else
                               g<<b[i]<<' ';

g.close();
return 0;
}