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

typedef struct Node {
    int val;
    struct Node* next;
} Node;

/* Inserare O(1) la începutul listei de adiacență */
static Node* push_adj(Node* head, int val) {
    Node* p = (Node*)malloc(sizeof(Node));
    if (!p) { perror("malloc"); exit(1); }
    p->val = val;
    p->next = head;
    return p;
}

/* BFS cu coadă pe vector (O(1) pe push/pop) */
static void bfs(int start, Node** adj, int n, int dist[]) {
    int *q = (int*)malloc(sizeof(int) * (n + 5));
    if (!q) { perror("malloc queue"); exit(1); }

    int st = 0, dr = 0;
    dist[start] = 0;
    q[dr++] = start;

    while (st < dr) {
        int u = q[st++];
        for (Node* p = adj[u]; p; p = p->next) {
            int v = p->val;
            if (dist[v] < 0) {
                dist[v] = dist[u] + 1;
                q[dr++] = v;
            }
        }
    }
    free(q);
}

/* Eliberare listă corectă (fără scăpări) */
static void free_list(Node* head) {
    while (head) {
        Node* nxt = head->next;
        free(head);
        head = nxt;
    }
}

int main(void) {
    FILE *fin = fopen("bfs.in", "r");
    FILE *fout = fopen("bfs.out", "w");
    if (!fin || !fout) { perror("fopen"); return 1; }

    int N, M, S;
    if (fscanf(fin, "%d %d %d", &N, &M, &S) != 3) {
        fprintf(stderr, "Eroare la citire N M S\n");
        return 1;
    }

    Node** adj = (Node**)calloc(N + 1, sizeof(Node*));
    int* dist = (int*)malloc(sizeof(int) * (N + 1));
    if (!adj || !dist) { perror("alloc"); return 1; }

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

    for (int i = 0; i < M; ++i) {
        int x, y;
        if (fscanf(fin, "%d %d", &x, &y) != 2) {
            fprintf(stderr, "Eroare la citirea muchiei %d\n", i);
            return 1;
        }
        /* graf orientat: arc x -> y */
        adj[x] = push_adj(adj[x], y);
    }

    bfs(S, adj, N, dist);

    for (int i = 1; i <= N; ++i) {
        fprintf(fout, "%d%c", dist[i], (i == N ? '\n' : ' '));
    }

    for (int i = 1; i <= N; ++i) free_list(adj[i]);
    free(adj);
    free(dist);
    fclose(fin);
    fclose(fout);
    return 0;
}