#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <string>
#include <limits>
#include <queue>
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

const int nMax = 100005;
int n, m, start, distanta[nMax];
vector <int> muchii[nMax];
queue <int> coada;

void bfs(){

    int nod;
    while(!coada.empty()){

         nod = coada.front();
         coada.pop();

         for(unsigned int i = 0; i < muchii[nod].size(); ++i){ //parcurg vecinii nodului
            if(distanta[muchii[nod][i]] == -1){
                coada.push(muchii[nod][i]);
                distanta[muchii[nod][i]] = distanta[nod] + 1;
            }
         }
    }
}

void citire(){
    fin >> n >> m >> start;

    for(int i = 1; i <= m; ++i){
        int a, b;
        fin >> a >> b;
        muchii[a].push_back(b);
    }

    for(int i = 1; i <= n; ++i)
        distanta[i] = -1;

    distanta[start] = 0;

    coada.push(start);

    bfs();
}


int main(){
    citire();

    for(int i = 1; i <= n; ++i)
        fout << distanta[i] << " ";

    return 0;
}