#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stack>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

void sol();

int main() {
#ifdef PADREATI
    freopen("in.txt", "r", stdin);
#else
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
#endif
    sol();
    return 0;
}

#define llu unsigned long long

#define N 100000
#define MAX 2000001

vector<int> G[N];


void sol() {
    int* q = (int*)malloc(MAX*sizeof(int));
    int* dist = (int*)malloc(N*sizeof(int));

    
    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);

    for (int i = 0; i < n; i++) {
        dist[i] = -1;
    }

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

    s--;
    dist[s] = 0;
    int start = 0;
    int end = 0;
    q[end++]=s;
    q[end++]=0;
    
    while(start<end) {
        int next = q[start++];
        int d = q[start++];
        dist[next]=d;
        for(vector<int>::iterator it=G[next].begin(); it!=G[next].end(); it++) {
            int value = *it;
            if(dist[value]!=-1) continue;
            q[end++]=value;
            q[end++]=d+1;
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");

}