#include <bits/stdc++.h>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
class Graph{
private:
        int n; //nr de noduri, nr de muchii, nodul de inceput
        int m;
        int s;
        vector<vector <int>> adj; // adj = adjacent
public:

    void BFS_read();
    void BFS();

};

void Graph::BFS_read(){

    fin>>n>>m>>s;
    int x,y;
    adj.resize(m+1);
    for(int i = 0; i < m; i++){
        fin>>x>>y;
        adj[x].push_back(y);
    }


}

void Graph::BFS(){
    bool *visited = new bool[n];
    int *length = new int[n];

    for(int i = 0; i < n; i++){
        visited[i] = false;
        length[i] = -1;
    }

    visited[s] = true;
    length[s] = 0;

    queue<int> q;
    q.push(s);

    while(!q.empty()){
        int curr_node = q.front();
        q.pop();
        int nr_vec = adj[curr_node].size();
        for(int i = 0; i<nr_vec;i++){
            int x = adj[curr_node][i];
            if(!visited[x]){
                visited[x] = true;
                q.push(x);
                length[x] = length[curr_node] + 1;
            }
        }

    }

    for(int i = 1; i <= n; i++){
        fout<<length[i]<<" ";
    }

}

int main()
{
    Graph test;
    test.BFS_read();
    test.BFS();
    fin.close();
    fout.close();

    return 0;
}