//
// Created by Octavian Farcasi on 24.10.2023.
//
#include<iostream>
#include<fstream>
#include<queue>
#include<unordered_map>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");

void citire(unordered_map<int,vector<int>> &lista,int nr_muchii){
    int m1,m2;
    while(nr_muchii){
        f>>m1>>m2;

        if(lista.find(m1)==lista.end())
            lista.insert({m1,vector<int>()});
        lista[m1].push_back(m2);

        nr_muchii--;
    }

}


void bfs(int nod_start, unordered_map<int,vector<int>> lista, vector<int> &rezultat, int nr_noduri){
    queue<int> coada;
    int copie;
    vector<bool>vizitate(nr_noduri,false);
    coada.push(nod_start);
    rezultat[nod_start-1]=0;
    vizitate[nod_start]=true;
    while(!coada.empty()){
        copie=coada.front();
        coada.pop();
        if(!lista[copie].empty()){
            for(auto &nod_d:lista[copie]){
                if(!vizitate[nod_d]){
                    coada.push(nod_d);
                    vizitate[nod_d]=true;
                    rezultat[nod_d-1]=rezultat[copie-1]+1;
                }
            }
        }
    }

}

int main() {

    int nr_nod,nr_muchii,nod_start;
    unordered_map<int,vector<int>>lista_adiac;
    f>>nr_nod>>nr_muchii>>nod_start;

    vector<int> rezultat(nr_nod,-1);
    citire(lista_adiac,nr_muchii);

    bfs(nod_start,lista_adiac,rezultat,nr_nod);

    for(auto &nr:rezultat)
        g<<nr<<" ";

}