#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

void BFS(vector<vector<int>> adj_matrix, int s, vector<int> &distance){
    queue<int> q;
    q.push(s);
    distance[s] = 0;
    vector<bool> visited(adj_matrix.size(), false);
    visited[s] = true;
    while(!q.empty()){
        int u = q.front();
	q.pop();
	for(unsigned int i = 0; i < adj_matrix[u].size(); ++i){
	    if(!visited[adj_matrix[u][i]]){
		distance[adj_matrix[u][i]] = distance[u] + 1;
	        q.push(adj_matrix[u][i]);
		visited[adj_matrix[u][i]] = true;
	    }
	}
    }
}

int main(){
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    unsigned int N, M;
    int x, y, s;
    fin >> N >> M >> s;
    s--;
    vector<vector<int>> adj_matrix(N, vector<int>());
    for(unsigned i = 0; i < M; ++i){
       fin >> x >> y; 
       adj_matrix[x - 1].push_back(y - 1);
    }
    vector<int> distance(N, -1);
    BFS(adj_matrix, s, distance);
    for(unsigned i = 0; i < N; ++i){
        fout << distance[i] << " ";
    }
    return 0;
}