#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

#define maxN 100005

using namespace std;
vector<int> arr[maxN];
int n, m, s, x, y, cnt, vizitatAndCost[maxN], Q[maxN], limitQ;
queue<int> q;

void citireMuchii() {
    for(int i = 1; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        arr[x].push_back(y);
    }
}

void afisareMuchii() {
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; (unsigned)j < arr[i].size(); ++j) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

void BFS_N(int nodStart) {
    memset(vizitatAndCost, -1, sizeof(vizitatAndCost));
    int currElem;

    // la inceput initializez limita cozii,
                // bag un singur element = nodul de start
                // specific faptul ca lungimea drumului e 0 de la start la start
    limitQ = 1;
    Q[limitQ] = nodStart;
    vizitatAndCost[nodStart] = 0;

    for(int i = 1; i <= limitQ; ++i) { // parcurg coada
        for(int j = 0; (unsigned)j < arr[Q[i]].size(); ++j) { // parcurg lista de adiacenta a ficarui element din coada
            currElem = arr[ Q[i] ][j];
            if (vizitatAndCost[ currElem ] == -1) { // nu a mai fost vizitat acest vecin (adica nu i s-a mai calc. costul)
                // incrementez limita cozii pentru ca sa mai adaug vecinul nevizitat si apoi il adaug
                Q[++limitQ] = currElem;
                // costul noului vecin care a fost acum adugat este costul nodului adiacent (cel care l-a bagat) + 1
                vizitatAndCost[ Q[limitQ] ] = vizitatAndCost[ Q[i] ] + 1;
            }
        }
    }
}

void BFS_STL(int nodStart) {
    memset(vizitatAndCost, -1, sizeof(vizitatAndCost));
    int currElem;

    q.push(nodStart);
    vizitatAndCost[nodStart] = 0;

    while(!q.empty()) {
        int qF = q.front();
        for(int j = 0; (unsigned)j < arr[qF].size(); ++j) {
            currElem = arr[qF][j];
            if(vizitatAndCost[ currElem ] == -1) {
                q.push(currElem);
                vizitatAndCost[ currElem ] = vizitatAndCost[qF] + 1;
            }
        }
        q.pop();
    }
}

int main() {
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &s);
    //printf("%d %d %d", n, m, s);
    citireMuchii();
    //printf("\n");
    //afisareMuchii();
    //BFS_N(s);
    BFS_STL(s);
    for(int i = 1; i <= n; ++i)
        printf("%d ", vizitatAndCost[i]);
    return 0;
}