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

using namespace std;

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

int cnt;

class graph{
    int V;
    list<int> *adj;
public:
    graph(int V){
        this -> V = V;
        adj = new list<int>[V];
    }
    void add_edge(int v, int w){
        adj[v].push_back(w);
        //adj[w].push_back(v);
    }
    void BFS(int start){
        bool *visited = new bool[V];
        int *cost = new int[V];
        for(int i = 0; i < V; i++){
            visited[i] = false;
            cost[i] = -1;
        }
        list<int> q;
        visited[start] = true;
        cost[start] = 0;
        q.push_back(start);
        while(!q.empty()){
            start = q.front();
            //cout << start << " ";
            q.pop_front();
            for(auto it = adj[start].begin(); it != adj[start].end(); it++){
                if(!visited[*it] and cost[*it] == -1){
                    visited[*it] = true;
                    q.push_back(*it);
                    cost[*it] = cost[start] + 1;
                }
            }
        }
        for(int i = 0; i < V; i++){
            out << cost[i] << " ";
        }
    }
    void DFS(int start, bool visited[]){
        visited[start] = true;
        //cout << start << " ";
        for(auto it = adj[start].begin(); it != adj[start].end(); it++){
            if(!visited[*it]){
                DFS(*it, visited);
            }
        }
    }
    void connectedComponents(){
        bool *visited = new bool[V];
        for(int v = 0; v < V; v++){
            visited[v] = false;
        }
        for(int v = 0; v < V; v++){
            if(!visited[v]){
                DFS(v, visited);
                cnt++;
            }
        }
        delete[] visited;
    }
};
int main()
{
    int n, m, start;
    in >> n >> m >> start;
    graph g(n);
    for(int i = 0; i < m; i++){
        int v, w;
        in >> v >> w;
        g.add_edge(v - 1, w - 1);
    }
    g.BFS(start - 1);
    return 0;
}