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

    using namespace std;

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

    class Graph
    {
        int V;
        list<int> *adj;
    public:
        Graph(int V);
        void addEdge(int v, int w);
        void BFS(int s);
    };

    Graph::Graph(int V)
    {
        this->V = V;
        adj = new list<int>[V];
    }

    void Graph::addEdge(int v, int w)
    {
        adj[v].push_back(w); // Add w to v’s list.
    }

    void Graph::BFS(int s)
    {
        bool *visited = new bool[V];
        bool *marked = new bool[V];
        int *muchii = new int[V];
        int cnt = 1;
        int rad = s;
        for(int i = 0; i < V; i++){
            visited[i] = false;
            muchii[i] = -1;
        }


        list<int> queue;


        visited[s] = true;
        queue.push_back(s);

        list<int>::iterator i;

        while(!queue.empty())
        {
            s = queue.front();

            queue.pop_front();

            int ok = 0;
            for (i = adj[s].begin(); i != adj[s].end(); ++i)
            {
                if (!visited[*i])
                {
                    visited[*i] = true;
                    if(!marked[*i]){
                        marked[*i] = true;
                        muchii[*i] = cnt;
                    }
                    queue.push_back(*i);
                    ok = 1;

                }
                else{
                    if(!marked[*i]){
                        marked[*i] = true;
                        muchii[*i] = 0;
                    }
                }

                // cout<<*i<<" ";

            }

            if(ok == 1)
                cnt++;
        }


        for(int i = 0; i < V; i++){
            g<<muchii[i]<<' ';
        }

    }


    int main()

        int N, M, S;
        f>>N>>M>>S;

        Graph g(N);
        for(int i = 0; i < M; i++){
            int z,w;
            f>>z>>w;
            g.addEdge(z-1,w-1);
        }

        g.BFS(S-1);

        return 0;
    }