#include <queue>
#include <iostream>

#include <cstdio>
using namespace std;

class Node;

class List {
    public:
        List *next;
        int node;

        List() {
            next = NULL;
            node = 0;
        }
};

class Node {
    public:
        int ind;
        List *edges;
        List *lastEdge;

        Node() {
            ind = 0;
            edges = new List;
            lastEdge = edges;
        }

        void addEdge(int x) {
            lastEdge->next = new List;
            lastEdge->node = x;
            lastEdge = lastEdge->next;
        }

        void setInd(int nr) {
            ind = nr;
        }
};

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

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

    Node G[n];

    for(int i = 0; i < n; ++i) {
        G[i].setInd(i);
    }

    for(int i = 0; i < m; ++i) {
        int x, y;

        scanf("%d %d", &x, &y);
        x--;
        y--;

        G[x].addEdge(y);
    }

    int dist[n];
    queue < Node > q;

    for(int i = 0; i < n; ++i) {
        dist[i] = -1;
    }

    dist[s] = 0;
    q.push(G[s]);

    while(!q.empty()) {
        Node x = q.front();
        q.pop();

        for(List *edge = x.edges; edge != NULL; edge = edge->next) {
            int y = edge->node;
            if(dist[x.ind] + 1 < dist[y] || dist[y] == -1) {
                q.push(G[y]);
                dist[y] = dist[x.ind] + 1;
            }
        }
    }

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

    return 0;
}