#include <iostream>
#include<vector>              //graful va fi pus in vectot
#include<queue>               //stack e sa punem nodurile curente pentru BFS
#include<fstream>
const int N = 100005;         //N e numarul maxim de varfuri in graph; 5 e de siguranta
using namespace std;
/* Cateva chestii: orice vectori mari ii
definesti in afara functiilor,caci altfel
se vor salva pe ceva numit stiva cre nu
poate tine atata memorie (asta e si motivul
[cred] pentru care recursivitatea e in
genmeralde evitat, ca toate variabilele
locale se retin in stiva). Orice e declarat
in afara corpului functiilor se intializeaza
cu 0; ce initializezi in functii au valori
randomsi nue bine sa le folosesti inainte de
ale declara*/

/*In general iti definesti constanta N ca mai
sus ca sa nu trebuiasca sa scrii graph[100005]
si dist[1000005],ca poti gresi la nr de zerouri*/

vector<int> graph[N];         //graph[i] vor fi varfurile vecine cu i
queue<int>  vert;             //varfurile curente pentru BFS
bool viz[N];                  //viz[i] = 0 daca inu a fost inca vizitat, 1 daca a fost vizitat
int dist[N];                  //dist[i] e distanta cautata pana la i
int n,m,v;                    //n = |V|,m = |E|,v varful de la care facem BFSul

void BFS(int v){              //BFS care porneste din v

    viz[v] = 1;               //v a fost vizitat
    vert.push(v);             //vert are momentan doar pe v; asta e modul in care pui elemente in stiva

    int curr;                 //varful curent, il vom folosi imediat
    vector<int>::iterator it; //iterator pentru vector; il vom folosi imediat

    while (!vert.empty()){    //functia asta e true daca vert nu mai are varfuri, adica daca tot graful (sau
                              //componenta conexa) afost parcursa
        curr = vert.front();  //cu top accesezi elementul din fata
        vert.pop();           //scoti elementul,canu mai ai nevoie de el

        it = graph[curr].begin();              //acum it e un pointer catre inceputul listei de vecini ai lui curr

        while (it != graph[curr].end()){       //end() e pointer catre finalul listei, sau mai degraba dupa finalul listei
                                               //adica end()-1 e finalul listei; begin in schimb e CHIAR inceputul
            if(!viz[*it]){                     //il adaugam doar daca e prima oara cand vedem;steluta e pentru ca it e pointer
                dist[*it] = dist[curr] + 1;    //am aflat distanta
                vert.push(*it);                //trebuie sa iladaugam
                viz[*it] = 1;                  //l-am vizitt
            }

            it++;                              //nu uita asta, sau altfel ai ciclu infinit
        }
    }

}

void Read(void){                                //funcie pentru  ciire
    ifstream f("bfs.in");

    f >> n >> m >> v;

    int a,b;
    int i;

    for(i=1; i<=m; i++){

            f >> a >> b;

            graph[a].push_back(b);              //adaugam pe b in lista de vecini a lui a;nu uita ca graphul e directionat
    }

}

void Print(void){                               //printam ce avem de printat

    ofstream g("bfs.out");

    int i;
    for(i=1; i<=n; i++){

        if  ( (dist[i] != 0) || (i == v) ){     //in mod normal ai printa direct dist[i], dar daca i nu e v si dist[i] = 0
                                                //atunci de fapt i si v NU sunt conectate
            g << dist[i] << " ";
        }

        else g << "-1 ";

    }
}
int main()
{
    Read();

    BFS(v);

    Print();

    return 0;
}