#include <stdio.h>
#include <iostream>
#include <vector>
#include <iterator>
#include <queue>

#define MAX 1000000
#define INF -1
using namespace std;

int parent[MAX];
int dist[MAX];

struct Node {

	int vertex; // node
 	int weight;

 	Node(int v, int w) {
 		vertex = v;
 		weight = w;
 	}

};

class Graph {

private:
	vector<Node> *adjList;
	int nodes_nr;

public:
	Graph(int V) {
		this->nodes_nr = V;
		adjList = new vector<Node>[V + 10];
	}
	~Graph() {
		delete[] adjList;
	}

	void addEdgeNode(int u, int v, int w = 1) {

		adjList[u].push_back(Node(v,w));
	}



	void BFS_Node(int root) {

		bool *visited = new bool;
		int node;
		
		queue<int> Q;
		vector<Node>::iterator it;
		
		//******** Initializing Graph Nodes ********

		for(int i = 0; i < this->nodes_nr; i++) {
			visited[i] = false;
			dist[i] = INF;
		}
		
		//******** Setting Root Nodes ********

		visited[root] = true;
		Q.push(root);
		dist[root] = 0;

		cout << "\nBFS_Node: ";

		while(!Q.empty()) {
		    
		    node = Q.front();
		    Q.pop();
		    cout << node << " ";
		    for(it = adjList[node].begin(); it != adjList[node].end(); ++it) {

		    	if(visited[it->vertex] == false) {

		    		visited[it->vertex] = true;
		    		dist[it->vertex] = dist[node] + 1;
		    		Q.push(it->vertex);
		    	}
		    }
		}
	}

};

int main(int argc, char **argv) {
	
	FILE *f;
	FILE *fwr;
	fwr = fopen("bfs.out", "w");
	if((f = fopen("bfs.in", "r")) == NULL) {
		fprintf(stderr, "Can't open file\n");
		return -1;
	}

	int N, M, root_node;
	int x,y;
	fscanf(f, "%d %d %d", &N, &M, &root_node);

	printf("N: %d , M: %d, Root : %d\n", N, M ,root_node );

	Graph graph_node(N);

	for(int i = 0; i < M; i++) {

		fscanf(f, "%d %d", &x, &y);
		graph_node.addEdgeNode(x,y,1);
	}

	cout << "Following is Breadth First Traversal (starting from vertex "<< root_node<< ") \n";
    
	graph_node.BFS_Node(root_node);
	cout << endl;
	
/*	for(int i = 1; i <= N; i++) {
		printf("%d -> %d, ", i, parent[i] );
		
	}
	//printf("\n");
	cout << endl; 
*/	
	cout << "Distance: ";
	for(int i = 1; i <= N; i++) {
		cout << dist[i] << " ";
		fprintf(fwr, "%d ", dist[i] );
	}
	cout << endl;
	

	fclose(f);
	return 0;
}




/*
	void addEdge(int u, int v) {

		adj[u].push_back(v);
	}

	void BFS(int root_node) {

		bool *visited = new bool();
		queue<int> Q;

		for(int i = 0; i < this->nodes_nr; i++) {
			visited[i] = false; // initializing all nodes to unvisited , aka WHITE
			cost[i] = 0;
			parent[i] = 0;
		}
		parent[this->nodes_nr] = 0;

		visited[root_node] = true; // marking root_node as visited, GRAY
		Q.push(root_node);

		vector<int>::iterator it;
		int node;

		while(!Q.empty()) {
			    
			node = Q.front();
			Q.pop();
			cout << node << " ";
		    for(it = adj[node].begin(); it != adj[node].end(); ++it) { // getting the neighbors of the root node

		    	if(visited[*it] == false) {
		    		//cost[*it]++;
		    		visited[*it] = true;
		    		Q.push(*it);		
		    		parent[*it] = node;
		    		//cost[parent[node]] = cost[*it] + 1; //TODO cost
		    		//cost[*it] = cost[node] + 1;
		    	}
		    }
		}
		//delete[] visited;
	}

	int *getParent() {
		return this->parent;
	}*/