#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>

#define WHITE 0
#define BLACK 1
#define GREY 2

std::vector<int> bfs(std::vector<std::vector<int>> vector, int source);

int main() {
    int N,M,S;
    std::vector<std::vector<int>> graph;

    FILE *in = fopen("bfs.in","r");
    FILE *out = fopen("bfs.out","w");

    fscanf(in,"%d",&N);
    fscanf(in,"%d",&M);
    fscanf(in,"%d",&S);

    for(int i = 0; i < N; i++) {
        std::vector<int> temp;
        graph.push_back(temp);
    }

    for(int i = 0; i < M; i++) {
        int start,end;
        fscanf(in,"%d %d",&start,&end);
        if(start != end) {
            graph[start - 1].push_back(end - 1);
        }
    }

    std::vector<int> result = bfs(graph,S - 1);

    for(int i = 0; i < result.size(); i++) {
        if ( result[i] == INT32_MAX ) {
            fprintf(out,"-1 ");
        }
        else {
            fprintf(out,"%d ", result[i]);
        }
    }

    fclose(in);
    fclose(out);
    return 0;
}

std::vector<int> bfs(std::vector<std::vector<int>> graph, int source) {
    std::vector<int> distance;
    int color[graph.size()];
    std::queue<int> Q;

    for(int i = 0; i < graph.size(); i++) {
        distance.push_back(INT32_MAX);
        color[i] = WHITE;
    }

    distance[source] = 0;
    color[source] = GREY;
    Q.push(source);

    while(!Q.empty()) {
        int top = Q.front();

        for(int neightbords : graph[top]) {
            if(color[neightbords] == WHITE) {
                distance[neightbords] = distance[top] + 1;
                color[neightbords] = GREY;
                Q.push(neightbords);
            }
        }
        color[top] = BLACK;
        Q.pop();
    }

    return distance;
}