#include <iostream>
#include <fstream>
#include <tuple>
#include <vector>
#include <queue>
#include <set>

using namespace std;

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

queue<int> deViz;
set<int> elemViz;

void parcurgereBFS(vector<int> *listaDeArce, int distPunctAles[], int &distanta) {
    // Retin valoarea ultimului element al cozii . Cand intalmim aceea valoare la inceput marim distanta, iar atunci retinem valoarea
    int deCres = deViz.back();

    while (deViz.empty() == 0) {
        // Luam primul element din coada
        int prElem = deViz.front();

        // Verificam daca este in set-ul de elemente parcurse

        distPunctAles[prElem] = distanta;

        // Iteram prin vectorul de arce al nodului respectiv si le puncem in coada daca nu au fost vizitate
        for (unsigned int i = 0; i < listaDeArce[prElem].size(); i++) {
            int elemVecin = listaDeArce[prElem][i];
            if (elemViz.find(elemVecin) == elemViz.end()) {
                elemViz.insert(elemVecin);
                deViz.push(elemVecin);
            }
        }

        if (deCres == prElem) {
            distanta++;
            deCres = deViz.back();
        }
        deViz.pop();
    }
}

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

    // Trebuie sa facem o lista de arce per nod: 1: 2,3
    vector<int> listaDeArce[n + 1];
    int distPctAles[n + 1];
    for (int i = 1; i <= n; i++)
        distPctAles[i] = -1;

    for (int i = 0; i < m; i++) {
        int source, destination;
        f >> source;
        f >> destination;
        listaDeArce[source].emplace_back(destination);
    }

    deViz.push(s);
    int distanta = 0;

    elemViz.insert(s);
    parcurgereBFS(listaDeArce, distPctAles, distanta);

    for (int i = 1; i <= n; i++)
        g << distPctAles[i] << ' ';

    // Am mod. fisierul de intrare si afisarea
    f.close();
    g.close();
    return 0;
}