// BFS.cpp : Defines the entry point for the console application.
//


#include <stdio.h>

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

using namespace std;
//Variable declarations
//---------------------------------------------------
int no_of_vertex, no_of_arches, source_vertex;


//--------------------------------------------------

//Function which read the data from a file passed as a parameter and create the adjacency list and initialize the visited array;
vector<vector<int>> read_data(string file_name){
	vector<vector<int>> ad_list;
	ifstream buf;

	buf.open(file_name);

	if (buf.good()){
		buf >> no_of_vertex;
		buf >> no_of_arches;
		buf >> source_vertex;

		ad_list.resize(no_of_vertex);

		for (int i = 0; i<no_of_arches; i++){
			int base, arrow;
			buf >> base;
			buf >> arrow;
			ad_list[base - 1].push_back(arrow);
		}
	}
	else
	{
		cout << "File was not open properly! ";
	}
	buf.close();
	return ad_list;

}



int* solution(vector<vector<int>>&& ad_list){
	typedef struct{
		int key;
		int cost;
	}NODE;

	int* vis = new int[no_of_vertex];
	for (int i = 0; i < no_of_vertex; i++){ vis[i] = -1; }

	queue<NODE> sol_queue;

	NODE aux;
	aux.key = source_vertex;
	aux.cost = 0;
	sol_queue.push(aux);

	while (!sol_queue.empty()){
		NODE extract;
		extract = sol_queue.front();
		sol_queue.pop();

		vis[extract.key - 1] = extract.cost;

		vector<int>::iterator it;
		for (it = ad_list[extract.key - 1].begin(); it != ad_list[extract.key - 1].end(); it++){
			if (vis[*it - 1] == -1){
				aux.key = *it;
				aux.cost = extract.cost + 1;
				sol_queue.push(aux);
			}
		}
	}

	return vis;

}


void write_to_file(string file_name, int* data){
	ofstream buf;
	buf.open(file_name);
	for (int i = 0; i < no_of_vertex; i++){
		buf << data[i] << " ";
	}
	delete[] data;
}

int main()
{

	write_to_file("bfs.out", solution(read_data("bfs.in")));


	return 0;
}