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

using namespace std;

ifstream f("bfs.in");
ofstream fout("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);
}

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;
                }
            }

        }

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


    for(int i = 0; i < V; i++){
        fout<<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;
}