#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
 
ifstream fin("bfs.in");
ofstream fout("bfs.out");
 
const int MAX_SIZE = 100005;
vector<int> graph[MAX_SIZE];
int distances[MAX_SIZE];
queue<int> positions;
 
void BFS() {
    while (!positions.empty()) {
        int currentPeak = positions.front();
        int size = graph[currentPeak].size();
        for (int i = 0; i < size; ++i) {
            int nextPeak = graph[currentPeak][i];
            if (distances[nextPeak] == -1) {
                distances[nextPeak] = distances[currentPeak] + 1;
                positions.push(nextPeak);
            }
        }
        positions.pop();
    }
}
 
int main() {
    int peaks, arches, startPeak;
    fin >> peaks >> arches >> startPeak;
    for (int i = 1; i <= arches; ++i) {
        int start, end;
        fin >> start >> end;
        if (start != end) {
            graph[start].push_back(end);
        }
    }
    positions.push(startPeak);
    for (int i = 1; i <= peaks; ++i) {
        distances[i] = -1;
    }
    distances[startPeak] = 0;
    BFS();
    for (int i = 1; i <= peaks; ++i) {
        fout << distances[i] << " ";
    }
    return 0;
}
/*
 
 Explicatie BFS:
 
 Ideea generala e sa stocam toate conexiunile (AKA muchiile orientate) intr-o lista de adiacenta.
 
 Inainte de a face parcurgerea propriu-zisa, am folosit un array pentru a stoca distantele de la punctul de start pana la un anumit varf din graf. De exemplu, sa zicem ca vrem sa ajungem de la 2 la 3, iar cel mai scurt drum are lungimea de "2". Atunci, pe pozitia 3 din acest array vom avea la final valoarea 2.
 
 Initial, acest sir va avea toate valorile pozitiilor initializate cu -1, mai putin valoarea pozitiei corespunzatoare punctului de la care plecam, care va fi egala cu 0.

Pornind de la punctul de start, ne folosim de o coada (prima oara coada va fi formata din doar un element, din punctul de start) pentru a stoca pozitiile pe care urmeaza sa ne deplasam. Vom iesi din aceasta structura pana cand nu vom mai avea elemente in coada.
 
 Vrem sa ne deplasam doar pe pozitiile unde nu am fost initial, astfel incat distanta sa fie minima. Astfel, iteram cu un for catre toate punctele adiacente cu punctul de la inceputul cozii (care prima data va fi exact punctul de start). La fiecare pas, daca valoarea pozitiei varfului adiacent din array-ul precizat mai sus este "-1" (adica nu ne-am mai deplasat pana acum spre el), il adaugam la finalul cozii, iar distanta corespunzatoare acestuia va lua valoarea distantei anterioare + 1.
 Dupa ce am iesit din "for-ul" care itereaza toate varfurile adiacente, eliminam din coada primul element.
 
 La final vom afisa array-ul care a stocat distantele
 
Pe exemplul din problema:
 5 7 2
 1 2
 2 1
 2 2
 3 2
 2 5
 5 3
 4 5
 -> distantele[]: -1 0 -1 -1 -1
 lista de adiacenta:
 1: 2
 2: 1, 5 (nu il mai adaugam pe 2 aici)
 3: 2
 4: 5
 5: 3
 
 queue: 2
 element curent = 2;
 iteram varfurile de adiacenta ale elementului curent: 1
 distanta de pe pozitia 1 e -1, deci distanta va deveni egala cu 0 + 1 = 1
 il adaugam in coada.
 queue: 2, 1
 iteram varfurile de adiacenta ale elementului curent: 5
 distanta de pe pozitia 5 e -1, deci distanta va deveni egala cu 0 + 1 = 1
 il adaugam in coada.
 queue: 2, 1, 5
 am terminat de iterat, il eliminam pe 2
 
 queue: 1, 5
 element curent = 1;
 iteram varfurile de adiacenta ale elementului curent: 2
 distanta de pe pozitia 2 e 0,  nu facem nici o operatie (ne-am deplasat deja pe 2, nu mai vrem lucrul asta pentru ca astfel am trece de mai multe ori prin acelasi punct)
 NU il adaugam in coada.
 queue: 1, 5
 am terminat de iterat, il eliminam pe 1
 
 queue: 5
 element curent = 5;
 iteram varfurile de adiacenta ale elementului curent: 3
 distanta de pe pozitia 3 e -1, deci distanta va deveni egala cu 1 (distanta pana la punctul 5 - elementul curent) + 1 = 2
 il adaugam in coada
 queue: 5, 3
 am terminat de iterat, il eliminam pe 5
 
 queue: 3
 element curent = 3;
 iteram varfurile de adiacenta ale elementului curent: 2
 distanta de pe pozitia 2 e 0, deci nu facem nici o operatie
 NU il adaugam in coada
 queue: 3
 am terminat de iterat, il eliminam pe 3 (primul element din coada)
 
 queue: goala, iesim din bucla
 
 Afisam distantele:
 1 2 3  4  5 - distanta pana la varful "i", unde "i" este o pozitie din array-ul distantelor
 1 0 2 -1 1
 
 Acolo unde nu va fi gasit un drum, se va afisa -1 (valoarea cu care au fost intializate toate distantele la inceput)
 
 
 
 */