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

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

int main() {
    int n, m, s;
    fin >> n >> m >> s;
    vector<vector<int>> lists(100000);

    // citim graful
    for (int i = 1; i <= m; ++i){
        int x, y;
        fin >> x >> y;
        lists[x].push_back(y);
    }

    // parcurgem cu bfs
    queue<int> nodes;
    vector<bool> visited(n + 1, false);
    vector<int> distante(n + 1, -1);

    nodes.push(s);  // nodul de start
    distante[s] = 0;
    visited[s] = true;

    while (!nodes.empty()){
        int nodCurent = nodes.front();  // nodul al carui vecini ii "accesam"
        nodes.pop();
        vector<int> listaNodCurent = lists[nodCurent];  // vecinii nodului

        while (!listaNodCurent.empty()){
            int vecin = listaNodCurent.front();
            if (visited[vecin] == false){
                distante[vecin] = distante[nodCurent] + 1;
                visited[vecin] = true;

                nodes.push(vecin);
            }
            listaNodCurent.erase(listaNodCurent.begin());
            
        }
    }

    for (int i = 1; i <= n; ++i){
        fout << distante[i] << " ";
    }

    return 0;
}