#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using namespace std;
#define maxn 100010
/*
 Se considera un graf orientat cu N varfuri si M arce.
 Fisierul de intrare bfs.in contine pe prima linie 3 numere intregi N M S,
 cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x y,
 cu semnificatia ca exista arc orientat de la x la y.
 In fisierul de iesire bfs.out se vor afla N numere separate prin spatiu cu
 semnificatia ca al i-lea numar reprezinta numarul minim de arce ce trebuie
 parcurse de la nodul S la nodul i.
 */
ifstream f("bfs.in");
ofstream g("bfs.out");
int vecin[maxn],distanta[maxn],S[maxn];

void BFS(int nod, vector<vector<int>>& lista_adiacenta){
    int i,j;
    for(int i=1;i<=lista_adiacenta.size()+1;i++){
        distanta[i]=-1;
    }
    int L=1;
    distanta[nod]=0;
    S[L]=nod;
    for(i=1;i<=L;i++){
        for(j=0; j<vecin[S[i]];j++){
            if(distanta[lista_adiacenta[S[i]][j]]==-1){
                S[++L]=lista_adiacenta[S[i]][j];
                distanta[S[L]]=distanta[S[i]]+1;
            }
        }
    }
}

///constructia listei de adiacenta
vector<vector<int>> constructieLista(int n,int m){
    int x,y;
    vector<vector<int>> lista_adiacenta(n+1);
//    lista_adiacenta[0].push_back(0);
    for(int i=1;i<=m;i++){
        f>>x>>y;
        lista_adiacenta[x].push_back(y);
    }
    return lista_adiacenta;
}
int main() {
    int n,m,Start;
    f>>n>>m>>Start;
    vector<vector<int>> Lista(n+1);
    Lista= constructieLista(n,m);
    for(int i=1;i<=n;i++){
        g<<i<<" : ";
        for(auto vecin:Lista[i])g<<vecin<<" ";
        g<<endl;
    }
    for (int i = 1; i <= n+1; i++)
        vecin[i] = Lista[i].size();
    BFS(Start,Lista);
    for (int i = 1; i <= n; i++)
        cout<<distanta[i]<<" ";
}