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

#define NMAX (100000)

typedef struct _node {
    int val;
    struct _node *next;
} node;

typedef struct _pair {
    int first;
    int second;
} pair;

int n, m, s;

node *list[NMAX];

int vis[NMAX];

int result[NMAX];

pair queue[NMAX];
int head = 0;
int tail = 0;

void push(pair el) {
    queue[tail] = el;

    tail = (tail + 1) % NMAX;
}

pair pop() {
    pair ret = queue[head];
    head = (head + 1) % NMAX;

    // Mark it as visited.
    vis[ret.first] = 1;

    return ret;
}

void insert(pair src) {
    node *p = list[src.first];

    while (p != NULL) {
        if (vis[p->val] == 0) {
            pair a;
            a.first = p->val;
            a.second = src.second + 1;
            push(a);
            result[a.first] = a.second;
        }
        p = p->next;
    }
}

void bfs(int src) {
    pair q;

    pair start;
    start.first = src - 1;
    start.second = 0;

    push(start);

    #if DEBUG
    for (int i = head; i < tail; ++i) {
        printf("(%d, %d) ", queue[i].first, queue[i].second);
    }
    printf("\n");
    #endif

    while (head != tail) {
        q = pop();
        insert(q);

        #if DEBUG
        for (int i = head; i < tail; ++i) {
            printf("(%d, %d) ", queue[i].first, queue[i].second);
        }
        printf("\n");
        #endif
    }
}


int main() {
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);

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

    // Must be cleared after we read n.
    memset(list, 0, sizeof(node*) * n);
    memset(vis, 0, sizeof(int) * n);
    memset(result, -1, sizeof(int) * n);
    result[s - 1] = 0;

    int i, t, a, b;
    node* p;

    t = m;
    for (; t; --t) {
        scanf("%d %d", &a, &b);
        #if DEBUG
        printf("%d %d\n", a, b);
        #endif

        if (list[a -1] == NULL) {
            #if DEBUG
            printf("branch 1\n");
            #endif

            list[a -1] = (node*) malloc(sizeof(node));
            list[a -1]->val = b - 1;
            list[a -1]->next = NULL;
        }
        else {
            #if DEBUG
            printf("else\n");
            #endif

            p = list[a -1];
            while (p->next != NULL) {
                p = p->next;
            }

            p->next = (node*) malloc(sizeof(node));
            p = p->next;
            p->val = b - 1;
            p->next = NULL;
        }
        #if DEBUG
        printf("end loop\n");
        #endif
    }

    #if DEBUG
    printf("\nPrinting children...\n");
    for (i = 0; i < n; ++i) {
        p = list[i];
        printf("%d\n", i);
        while (p != NULL) {
            printf("%d ", p->val);
            p = p->next;
        }
        printf("\n\n");
    }
    #endif

    bfs(s);

    for (i = 0; i < n; ++i) {
        printf("%d ", result[i]);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}