#include <fstream>
#include <vector>
#include <queue>

#define maxi 100001

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

class Graf {
    int nrNoduri, nrMuchii;
    int x, y; // extremitate muchie stanga respectiv dreapta
    int vizitat[maxi] = {0}; // vector pentru marcarea vizitelor

    vector<int> *adiacenta; // lista de vecini
    queue<int> coada;

public:
    Graf();
    ~Graf();

    void citireBFS(int &nodPlecare);
    void BFS();
    void afisareCoadaBFS();
};

Graf::Graf() {
    nrNoduri = nrMuchii = x = y = 0;
    adiacenta = new vector<int>[maxi];
}

Graf::~Graf() {
    delete[] adiacenta;
}

void Graf::citireBFS(int &nodPlecare) {
    fin >> nrNoduri >> nrMuchii >> nodPlecare;  // Citește numărul de noduri, muchii și nodul de start
    for (int i = 1; i <= nrMuchii; i++) {
        fin >> x >> y;
        adiacenta[x].push_back(y);             // Adaugă muchia în lista de adiacență
    }
    for (int i = 1; i <= maxi; i++)
        vizitat[i] = -1;                       // Inițializează toate nodurile ca fiind nevizitate (-1)
    coada.push(nodPlecare);                    // Adaugă nodul de start în coadă
    vizitat[coada.back()] = 1;                 // Marchează nodul de start ca vizitat
}

void Graf::BFS() {
    while (!coada.empty()) {                   // Cât timp există noduri în coadă
        int nodPlecare = coada.front();        // Preia nodul din fața cozii
        for (auto i: adiacenta[nodPlecare])    // Parcurge toți vecinii nodului
            if (vizitat[i] == -1) {            // Dacă vecinul nu a fost vizitat
                vizitat[i] = vizitat[nodPlecare] + 1;  // Actualizează distanța față de nodul de start
                coada.push(i);                 // Adaugă vecinul în coadă
            }
        coada.pop();                           // Elimină nodul curent din coadă
    }
}

void Graf::afisareCoadaBFS() {
    for (int i = 1; i <= nrNoduri; i++) {      // Parcurge toate nodurile
        if (vizitat[i] == -1)                  // Dacă nodul nu a fost vizitat
            fout << -1 << " ";
        else
            fout << vizitat[i] - 1 << " ";     // Afișează distanța (corectată cu -1)
    }
}

int main() {
    int nodPlecare;
    Graf g1;
    g1.citireBFS(nodPlecare);
    g1.BFS();
    g1.afisareCoadaBFS();

    fin.close();
    fout.close();
    return 0;
}