#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <queue>

std::ifstream bfsin("bfs.in");
std::ofstream bfsout("bfs.out");

using namespace std;

class Link {
private:
    unsigned from;
    unsigned to;
public:
    Link(unsigned from, unsigned to): from(from), to(to) {}
    unsigned getTo() {
        return this->to;
    }

};


class Graph {
private:
    unsigned V;
    std::list<Link> *adj;

    void BFSUtil(unsigned start, int *out) {
        std::queue<unsigned> q;

        q.push(start);
        out[start] = 0;

        while(!q.empty()) {
            unsigned v = q.front();
            q.pop();
            for(auto it : adj[v]) {
                if(out[it.getTo()] == -1) {
                    out[it.getTo()] = out[v] + 1;
                    q.push(it.getTo());
                }
            }
        }
    }

public:
    Graph(unsigned V): V(V) {
        adj = new std::list<Link>[V + 1];
    }

    void addEdge(unsigned from, unsigned to) {
        Link link(from, to);
        adj[from].push_back(link);
    }

    void BFS(unsigned start) {
        int *out = new int[this->V + 1];
        for(unsigned i = 1; i <= this->V; i ++) {
            out[i] = -1;
        }

        BFSUtil(start, out);
        for(unsigned i = 1; i <= this->V; i ++) {
            bfsout << out[i] << " ";
        }
        delete[] out;
    }

};


int main() {
    unsigned long n, m, s, a, b;
    bfsin >> n >> m >> s;
    auto G = new Graph(n);
    for (unsigned i = 0; i < m; i ++) {
        bfsin >> a >> b;
        G->addEdge(a, b);
    }
    G->BFS(s);
    return 0;
}