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

using namespace std;


int n;

void bfs(int source, vector< vector<int> > lista, int dist[], int visited[]){
	visited[source] = 1;
	dist[source] = 0;
	
	queue<int> q;
	q.push(source);
	
	int node;
	
	while(!q.empty()){
		
		node = q.front();
		q.pop();
		
		cout<<"Din nodul :"<<node<<endl;
		
		for(int i=0; i<lista[node].size(); i++){
			if(visited[ lista[node][i] ] == 0){
				cout<<"adaug "<<lista[node][i]<<endl;
				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();

	int visited[n+1];
	int dist[n+1];
	
	for(int i=1; i<=n; i++){
		visited[i] = 0;
		dist[i] = -1;
	}
	
	bfs(source, lista, dist, visited);

}