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

using namespace std;


int n;

void bfs(int source, vector< vector<int> > lista){
	vector<int> visited(n+1, 0);
	vector<int> dist(n+1, -1);

	visited[source] = 1;
	dist[source] = 0;
	
	queue<int> q;
	q.push(source);
	
	int node,len;
	
	while(!q.empty()){
		
		node = q.front();
		q.pop();

		len = lista[node].size();
		for(int i=0; i<len; i++){
			if(visited[ lista[node][i] ] == 0){
				visited[ lista[node][i] ] = 1;
				q.push( lista[node][i] );
				dist[ lista[node][i] ] = dist[node] + 1;
			}
		}	
	}
	
	ofstream out("bfs.out");
	for(int i=1; i<=n; i++)
		out<<dist[i]<<" ";
	out.close();
}


int main(){

	ifstream in("bfs.in");
	
	int m,source;
	in>>n>>m>>source;
	
	vector< int > aux;   
    vector< vector <int> > lista(n+1, aux);
	
	int x,y;
    for(int i=0; i<m; i++){
    	in>>x>>y;
    	lista[x].push_back(y);
    }
    
    in.close();

	bfs(source, lista);

}