#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

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

const int DIMN = 100005;

// vector<int> graf[DIMN];

// int dist[DIMN];

int main() {
    int N, M, src;
    cin >> N >> M >> src;
    vector<vector<int>> graf(N + 1); // initializez graf cu N+1 vectori vizi
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        graf[x].push_back(y);
    }

    // memset(dist, -1, sizeof dist); // initializeaza toti octetii din dist cu -1
    // -1 in binar este 11111111 => in 4 octeti: 11111111111111111111111111111111 (tot -1)
    // cu 5 nu merge: 00000101 => 00000101000001010000010100000101
    vector<int> dist(N + 1, -1); // vector de N+1 elemente initializate cu -1

    queue<int> q; // local se retin foarte putine date, elementele adaugate in coada sunt alocate pe HEAP
    q.push(src);
    dist[src] = 0;
    while (!q.empty()) {
        int nod = q.front();
        q.pop();

        for (int vecin : graf[nod]) {
            if (dist[vecin] != -1)
                continue;
            dist[vecin] = dist[nod] + 1;
            q.push(vecin);
        }
    }

    for (int i = 1; i <= N; ++i)
        cout << dist[i] << ' ';

    return 0;

}