/*
    Exemplificare BFS

    http://www.infoarena.ro/problema/bfs
*/

#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <bitset>
#include <cassert>
#include <queue>
#include <cstring>
// de obicei cunosc aceste limite pentru problema mea (se dau in enunt)
#define NMAX 100009 // numarul maxim de noduri din fisier
#define MMAX 1000009 // numarul maxim de muchii din fisier
#define oo (1 << 30) // infinit :D
using namespace std;


// urmatoarele 2 linii sunt pentru infoarena, pt ca la ei streamurile sunt mai rapide
// pe vmcheker nu sunt (e vorba doar de modul de citire. puteti ignora)
ifstream in("bfs.in");  // daca nu imi pasa de infoarena, sterg astea 2 linii
#define cin in          // si decomentez deschiderea de fisier din main

int n; // numarul de noduri pe testul curent
int m; // numarul de muchii pe testul curent
int s; // sursa de la BFS

// graful stocat ca liste de adiacenta
// G[i] = un vector == lista de adiacenta a lui i (nodurile vecine cu i)
// Pentru eficienta G[i] este un vector resizable
vector<int> G[NMAX];

// o coada in care bag nodurile de vizitat
queue<int> Q;

// d[i] = distanta de la SURSA la nodul i (in cazul problemeri curent este numarul de arce)
int d[NMAX];

// alte chestii utile
// exemplu: p[i] = parintele lui i din arborele BFS
int p[NMAX];

void read_input() {
    // citeste n si m
    cin >> n >> m >> s;

    // citesc muchiile
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >>  x >> y; // daca avea cost puneam si  >> c;

        // adaug muchia x -> y ( in problema asta e orientat)
        G[x].push_back(y); // x -> y
    }
}

void BFS(int source) {
    // ETAPA 1
    // in general pentru fiecare nod pun valori initiale
    // in structurile de mai sus
    for (int i = 1; i <= n; ++i) {
        d[i] = oo; // distanta de la S la i e infinit initial
        p[i] = oo; // initial nu cunosc parintele lui i
    }

    // ETAPA 2
    // bag sursa in coada
    Q.push(source);
    d[source] = 0; // distanta de la source la source e 0
    p[source] = 0; // source e root, nu are parinte

    // ETAPA 4
    // cat timp coada nu e goala, mai am ceva de vizitat
    // vizitez toti vecinii lui
    while (!Q.empty()) {
        // extrag si sterg din coada primul nod de vizitat
        int node = Q.front();
        Q.pop();

        // fac ceva pentru el daca e cazul  - la alte probleme
        // cout << node << " "; // daca sunt curios sa vad in ce ordine sunt parcurse nodurile

        // ca la DFS, parcurg lista de adiacenta a lui node
        // vizitez vecinii (Daca are sens)
        for (auto it = G[node].begin(); it != G[node].end(); ++it) {
            // momentan stiu asta
            // am drum : sursa -> ... -> node de cost d[node]
            // am drum : sursa -> ... -> *it de cost d[*it]
            // verific daca sursa -> ... -> node -> *it e un drum mai scurt de la sursa la *it
            if (d[ node ] + 1 < d[ *it ]) {
                // ok il actualizez pe *it pt ca i-am gasit un drum mai scurt
                d[ *it ] = d[ node ] + 1; // noua distanta
                p[ *it ] = node ; // parinte lui *it este node

                // adaug in coada pe *it, ca sa il vizitez si pe el
                // cand o sa ii vina randul
                Q.push( *it ); // citeste *** de dupa main
            }
        }
    }

    // aici de obicei fac clean-up
    // de exemplu eu am codificat cu d[i] = oo; daca nu pot ajunge de la
    // source la i, dar pe infoarena vrea sa pun -1
    for (int i = 1; i <= n; ++i) {
        if (d[i] == oo) {
            d[i] = -1;
        }
    }
}


// in solve scriu tot ce tine de rezolvare - e ca un main
void solve() {
    BFS(s);
}


// afisez vectori si tot ce mai trebuie
void print_output() {
    for (int i = 1; i <= n; ++i) {
        cout << d[i] <<  " ";
    }
    cout << "\n";
}



// puteti pastra main-ul mereu cum e acum
int main() {
    // las linia urmatoare daca citesc din fisier
    // assert( freopen("bfs.in", "r", stdin) != NULL);

    // las linia urmatoare daca afisez in fisier
    assert( freopen("bfs.out", "w", stdout) != NULL) ;

    read_input();
    solve();
    print_output();

    return 0;
}

// ***
// observatie: puteti sa va tineti minte un bitset
// inQ[ i ] = 1, daca i este deja in coada, 0 altfel
// si sa il baga pe *it in coada doar daca nu este
// complexitatea nu este afectata, dar o sa aveti o surpriza
// mare: pentru unele probleme timpul de rulare este mult mai mic
// daca nu adaug de mai multe ori pe *it in coada
// Obs: daca il adaug de mai multe ori, doar o data fac ceva cu el,
// celelate aparitii sunt degeaba! - pentru ca un nod
// scos din coada la BFS este deja "rezolvat", asa ca prima oara
// isi poate actualiza vecinii, a doua oara pentru ca el nu se schimba,
// nici nu ae ce sa le mai faca vecinilor