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

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, bool *visited, int *out) {
        std::queue<std::pair<int, unsigned>> q;

        q.push(std::make_pair(0, start));

        while(!q.empty()) {
            unsigned v = q.front().second;
            unsigned c = q.front().first;
            q.pop();
            if (!visited[v]) {
                visited[v] = true;
                out[v] = c;
                for(auto it : adj[v])
                    q.push(std::make_pair(c + 1, 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 printGraph() {
        for(unsigned i = 1; i <= this->V; i ++) {
            for(auto it : adj[i]) {
                std::cout << "nodul " << i << " este conectat cu " << it.getTo() << std::endl;
            }
        }
    }

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

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

};


int main() {
    std::ifstream in("bfs.in");
    std::ofstream out("bfs.out");
    unsigned long n, m, s, a, b;
    in >> n >> m >> s;
    auto G = new Graph(n);
    for (unsigned long i = 0; i < m; i ++) {
        in >> a >> b;
        G->addEdge(a, b);
    }
    G->BFS(s);
    return 0;
}