#include <iostream>
#include <fstream>
using namespace std;

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


typedef struct d{bool viz;int lung;};

d* vec;

int* raspuns;

nod CreareNod(int x)
{
    nod aux = new a;
    aux->val = x;
    aux->next = NULL;
    return aux;
}

lista CreareLista(int x)
{
    lista a = new nod[x+1];
    for(int i=1;i<=x;i++)
        a[i]=NULL;
    return a;
}

void AdaugareLeg(lista &l,int x,int y)
{
    nod toadd = CreareNod(y);
    nod aux;

    if(l[x]==NULL)
        l[x]=toadd;

    else
    {
        aux=l[x];
        while(aux->next!=NULL)
            aux=aux->next;
        aux->next = toadd;
    }

}


lista input_legaturi_start(int &noduri,int &legaturi,char *nume,int &start)
{
    fstream f(nume,ios::in);
    f>>noduri>>legaturi>>start;

    //cout<<"uhm";
    vec = new d[noduri+1];
    raspuns = new int[noduri+1];
    for(int i=1;i<=noduri;i++)
    {
        //cout << "s";
        vec[i].viz=0;
        vec[i].lung=0;
        raspuns[i]=-1;
    }

    //cout << "?";
    lista a = CreareLista(noduri);
    for(int i=1;i<=legaturi;i++)
    {
        int x,y;
        f>>x>>y;
        if(x==y)
            raspuns[x]=0;
        AdaugareLeg(a,x,y);
    }
    //cout<<"a";
    return a;


}



void citire_lista(lista l,int noduri,int legaturi)
{
    for(int i=1;i<=noduri;i++)
    {
        cout << i << ": ";
        if(l[i]!=NULL)
        {
            nod aux=l[i];
            while(aux!=NULL)
                  {
                      cout << aux->val << ", ";
                      aux=aux->next;
                  }

        }
        cout << "\n";
    }
}





void bfs_info_arena(lista la,int noduri,int start)
{

    int l=0,index=1,actual;
    int coada[noduri+1];
    nod aux;


    coada[index]=start;
    vec[start].viz=1;
    while(index>0)
    {
        actual = coada[index];
        index--;

        for(aux=la[actual];aux!=NULL;aux=aux->next)
        {
            int val=aux->val;
            if(vec[val].viz==0)
            {
                index++;
                coada[index]=val;
                vec[val].viz=1;
                vec[val].lung=vec[actual].lung+1;
            }

            if(raspuns[val]==-1)
                raspuns[val]=vec[actual].lung+1;
        }

    }


}


void afisare_raspuns(int noduri)
{   cout << "raspuns:  ";
    for(int i=1;i<=noduri;i++)
        cout << raspuns[i] << " ";
    cout << endl;
}



int main()
{
    int noduri,legaturi,start;
    lista la = input_legaturi_start(noduri,legaturi,"bfs.in",start);
    citire_lista(la,noduri,legaturi);
    bfs_info_arena(la,noduri,start);
    afisare_raspuns(noduri);


}