#include <fstream>
#include <vector>
#include <cstring>

#define Nmax 100100
#define oo (1 << 30)

using namespace std;

struct Node {
    int item;
    Node * next;
    Node() {
        next = NULL;
    }
};

class Queue {

    public:

        Node * first, * last;

        Queue() {
            first = last = NULL;
        }

        void push(int newItem) {

            Node * node = new Node;
            node->item = newItem;

            if(last == NULL)
                first = node;
            else
                last->next = node;
            last = node;
        }

        void pop() {

            Node * node = first;

            if(first->next == NULL)
                first = last = NULL;
            else
                 first = first->next;

            delete node;
        }

        int front() {
            return first->item;
        }

        int back() {
            return last->item;
        }

        Node * begin() {
            return first;
        }

        Node * end() {
            return last;
        }

        bool empty() {
            return (first == NULL);
        }
};

class Graph {

    private:
        Queue List[Nmax];
        bool seen[Nmax];
        int size;

    public:
        Graph() {
            memset(seen, 0, sizeof(seen));
        }

        void initialize(int Size) {
            size = Size;
        }

        void addEdge(int x, int y) {
            List[x].push(y);
        }

        vector <int> bfs(int Start) {

            int i, node;
            vector <int> distance;
            Queue queue;
            Node * neighbour;

            for(i = 1; i <= size; i++)
                distance.push_back(oo);

            queue.push(Start);
            seen[Start] = true;
            distance[Start - 1] = 0;

            while(!queue.empty()) {

                node = queue.front();
                queue.pop();

                for(neighbour = List[node].begin(); neighbour != NULL; neighbour = neighbour->next)
                    if(!seen[neighbour->item]) {
                        queue.push(neighbour->item);
                        seen[neighbour->item] = true;
                        distance[neighbour->item - 1] = distance[node - 1] + 1;
                    }
            }

            return distance;
        }
};

Graph graph;
int N, Start;

void Read() {

    int x, y, M;
    ifstream in("bfs.in");

    in >> N >> M >> Start;
    graph.initialize(N);

    while(M--) {
        in >> x >> y;
        graph.addEdge(x, y);
    }

    in.close();
}
void Write() {

    vector <int> solution = graph.bfs(Start);
    ofstream out("bfs.out");

    for(int i = 0; i < solution.size(); i++)
        out << (solution[i] == oo ? -1 : solution[i]) << ' ';

    out << '\n';
    out.close();
}
int main() {

    Read();
    Write();

    return 0;
}