#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>

using namespace std;

#define kMaxEdges 100005

class Graph {
    public:
        vector <int> edges[kMaxEdges];
};

queue <int> Q;
int cost[kMaxEdges];

int main()
{
    int N, M, S;

    ifstream f ("bfs.in");
    ofstream out ("bfs.out");

    f >> N >> M >> S;

    for (int i = 1; i <= N ; ++i) {
        cost[i] = -1;
    }

    int x , y;
    Graph g;

    while (M --) {
        f >> x >> y;

        g.edges[x].push_back(y);
    }

    cost[S] = 0;
    Q.push(S);

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

        for (unsigned int i = 0 ; i < g.edges[queueNode].size(); ++i) {
            int neighbourNode = g.edges[queueNode][i];

            if (cost[neighbourNode] != -1) continue;

            cost[neighbourNode] = cost[queueNode] + 1;
            Q.push(neighbourNode);
        }
    }

    for (int i = 1; i <= N; ++i) {
        out << cost[i] << " ";
    }

    return 0;
}