#include <stdio.h>

#define IN "bfs.in"
#define OUT "bfs.out"
#define MAXN 100001

typedef struct _GRAPH{
    int nextNode;
    struct GRAPH *next;
} GRAPH;

int s, n, m, seen[MAXN];
GRAPH *graph[MAXN];

void read (void){
    int i, node, edge;
    scanf ("%d%d%d", &n, &m, &s);

    for (i = 1; i <= m; ++i){
        scanf ("%d%d", &node, &edge);
        GRAPH *p = (GRAPH*) malloc (sizeof (GRAPH));
        p -> nextNode = edge;
        p -> next = graph[node];
        graph[node] = p;
    }
}

void init(void){
    int i;
    for (i = 1; i <= n; ++i)
        seen [i] = -1;
}

void printSolution (void){
    int i;
    for (i = 1; i <= n; ++i)
        printf ("%d ", seen[i]);
}

void BFS (int lev){
    int left = 1, right = 1, tail[MAXN];
    tail [right] = s;
    seen [tail [left]] = 0;
    GRAPH *node;

    while (left <= right){
        node = graph [tail [left]];

        while (node){
            if (seen [node -> nextNode] == -1){
                seen [node -> nextNode] = seen [tail [left]] + 1;printf ("%d\n", seen [tail[left]]);
                tail [++ right] = node -> nextNode;
            }
            node = node -> next;
        }

        ++ left;
    }

    printSolution ();
}

int main (void){
    freopen (IN, "r", stdin);
    freopen (OUT, "w", stdout);

    read();
    init();
    BFS(s);

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