#include<stdio.h>
#include<stdlib.h>

#define MAX_N 100001
int N, M, S;

struct arc {
    int d; // dest node value
    struct arc *next;
};

struct arc *adj[MAX_N];
int cost[MAX_N];
int visit[MAX_N];

struct queue {
    struct arc *head;
    struct arc *tail;
    int size;
} Q;


void add_arc(int x, int y) {
    struct arc *q = calloc(sizeof(struct arc), 1);
    q->d = y;
    q->next = adj[x];
    adj[x] = q;
}

void push(struct arc *p) {
    if(visit[p->d])
        return;
    visit[p->d] = 1;
    struct arc *q = calloc(sizeof(struct arc), 1);
    q->d = p->d;
    q->next = NULL;
    if(0 == Q.size) {
        Q.head = q;
        Q.tail = q;
    } else {
        Q.tail->next = q;
        Q.tail = q;
    }
    Q.size++;
}

void pop(struct arc **p) {
    if(0 == Q.size) {
        *p = NULL;
        return;
    }
    *p = Q.head;
    Q.head = Q.head->next;
    Q.size--;
}

void print_cost()
{
    for(int i = 1; i <= N; i++) {
        printf("%d\t", cost[i]);
    }
    printf("\n");
}

int main(void)
{
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    scanf("%d %d %d", &N, &M, &S);

    Q.head = NULL;
    Q.tail = NULL;

    for(int i = 1; i<= N; i++) {
        adj[i] = NULL;
        cost[i] = -1;
    }

    cost[S] = 0;

    for(int i = 0; i < M; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        add_arc(x,y);
    }

    struct arc *z = calloc(sizeof(struct arc), 1);
    z->d = S;
    z->next = NULL;
    push(z);
    struct arc *p = NULL;
    while(Q.head != NULL) {
        pop(&p);
        struct arc *q = adj[p->d];
        while(q) {
            if(!visit[q->d]) {
                cost[q->d] = cost[p->d] + 1;
                push(q);
            }
            q = q->next;
        }
        free(p);
    }
    print_cost();
    return 0;
}