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

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

class Graf{

    private:
        int noduri, muchii;
        vector <vector<int>> adiacenta;
        vector<int> cost_vizita;
public:
    Graf(); //constructor neparametrizat
    Graf(int nr_noduri, int nr_muchii); //constructor parametrizat - in functie de nr de noduri si muchii
    ~Graf(); //destructorul

    void Muchie(int tata, int fiu); //adaug o muchie in graful curent
    void BFS(int sursa);
};
Graf::Graf() //constructor neparametrizat - valori implicite = 0
{
    this->noduri = 0;
    this->muchii = 0;
}
Graf::Graf(int nr_noduri, int nr_muchii) //constructor parametrizat - in functie de nr de noduri si muchii
{
    this->noduri = nr_noduri; //initializez dimensiunile grafului cu cele citite din fisier
    this->muchii = nr_muchii;
    adiacenta.resize(nr_noduri, std::vector<int>(nr_muchii)); //definesc o lista de adiacenta sub forma unui vetor de vectori de dimensiune (nr_noduri * nr_muchii)
    cost_vizita.resize(nr_noduri, -1); //definesc un vector unde contorizez pe parcursul BFS-ului ce noduri au fost vizitate si care e distanta catre nodul parinte, initializarea se face cu valoarea -1
}
Graf::~Graf() //destructorul
{ 
    this->noduri = 0;
    this->muchii = 0;
    for (int i = 0; i < adiacenta.size(); i++) //eliberez spatiul alocat vetorului de vectori, stergand linie cu linie elementele
        adiacenta[i].clear();
    cost_vizita.clear(); //eliberez spatiul alocat vectorului unde contorizez nodurile vizitate
}
void Graf::Muchie(int tata, int fiu) 
{
    adiacenta[tata - 1].push_back(fiu - 1); //adaug pe linia tata - 1, ca ultim element al vetorului, nodul cu care se invecineaza (fiu - 1) - le adaug -1 pentru ca eu lucrez cu vectori care incep de la 0
}
void Graf::BFS(int sursa)
{
    queue<int> vecini; //coada in care aduag pe rand nodurile pe care le voi parcurge in BFS
    cost_vizita[sursa - 1] = 0; //costul de vizita al nodului sursa e 0
    vecini.push(sursa - 1); //adaug nodul sursa in BFS
    while (!vecini.empty()) { //cat timp am noduri accesibile din radacina
        int nod_curent = vecini.front(); //iau nodul din fata cozii si adaug la finalul cozii toti vecinii cu care acesta are conexiuni
        vecini.pop();
        for (int i = 0; i < adiacenta[nod_curent].size(); i++) //iau din lista de adiacenta nodurile vecine
        {
            if (cost_vizita[adiacenta[nod_curent][i]] < 0) { //verific ca nodul sa nu fi fost deja vizitat
                cost_vizita[adiacenta[nod_curent][i]] = cost_vizita[nod_curent] + 1; //daca nodul nu a fost vizitat, ii calculez costul de vizita
                vecini.push(adiacenta[nod_curent][i]);                               //si il adaug in coada pentru BFS
            }
        }
    }
    for (int i = 0; i < cost_vizita.size(); i++) //afisez costul pentru fiecare nod
       g << cost_vizita[i] << " ";
}
int main() {
    int N, M, S, x, y;
    f >> N >> M >> S;
    Graf exbfs(N, M); //initializez graful
    for (int i = 0; i < M; i++)
    {
        f >> x >> y;
        exbfs.Muchie(x, y);
    }
    exbfs.BFS(S); 
    return 0;
}