//Fiind dat un nod S, sa se determine, pentru fiecare nod X,
//numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul sursa S la nodul X.


//Parcurgerea in latime (BFS - Breadth First Search)
//Complexitatea alg este:
//	cu liste de adiacenta - O(n+m)
//	cu matricea de adiacenta - O(n^2)
#include <iostream>
#include <fstream>
using namespace std;

void citireGrafOrientat(int** &, int&, int&);
void afisare(int* , int);

//altele
void deleteArray(int* A[], int);
int* myRealloc(int A[], int);
void BFS(int* A[],int* viz,int* C,int* v, int x);

int main(void)
{
	//numarul de varfuri din graf
	int n;
	//nodul de plecare
	int s;
	int** A;

//	cout << "Graf Orientat: " << endl;

	citireGrafOrientat(A, n, s);

	//vec vizitelor
	int* viz = new int[n];
	for (int i = 0; i <= n; i++)
		viz[i] = 0;
	
	//Coada
	int* C = new int[n];

	//vec nr vizita
	int* v = new int[n];

	//init vect cu -1
	for (int i = 1; i <= n; i++)
		v[i] = -1;
	v[s] = 0;

	BFS(A,viz,C,v,s);
	afisare(v, n);
	deleteArray(A, n);
	delete[] C;
	delete[] v;
	delete[] viz;
	return 0;
}

void citireGrafOrientat(int** &A, int& n, int& s)
{
	int x, y;
	//numarul de muchii
	int m;
	fstream fin("bfs.in", ios::in);
	fin >> n >> m >> s;

	A = new int*[n];

	for (int i = 1; i <= n; i++)
	{
		A[i] = new int[1];
		A[i][0] = 0;
	}

	for (int i = 1; i <= m; i++)
	{
		fin >> x >> y;
		//incrementez gradul varfului x
		A[x][0]++;
		//realoc memorie pentru lista de adiacenta a lui x
		///A[x] = (int*)realloc(A[x], (A[x][0] + 1) * sizeof(int));
		A[x] = myRealloc(A[x], A[x][0] + 1);
		//memoram pe y in lista de adiacenta a lui x
		A[x][A[x][0]] = y;
	}
	fin.close();
}

void afisare(int* v, int n)
{
	ofstream fout("bfs.out");
	for (int i = 1; i <= n; i++)
		fout << v[i] << ' ';
	fout << endl;
	fout.close();
}

void BFS(int* A[], int* viz, int* C, int* v, int x)
{
	int prim, ultim;
	//vizitez varful de start
//	cout << x << ' ';
	viz[x] = 1;
	//init coada cu varful de start
	C[0] = x; prim = ultim = 0;
	while (prim <= ultim) //cat timp coada nu este goala
	{
		//extrag primul element din coada
		x = C[prim++];
		for (int i = 1; i <= A[x][0]; i++)
		{
			if (!viz[A[x][i]])  //daca vecinul A[x][i] nu este vizitat
			{
				v[A[x][i]] = v[x] + 1;
//				cout << A[x][i] << ' ';
				viz[A[x][i]] = 1;		//il marchez ca vizitat
				C[++ultim] = A[x][i];	//il plasez in coada
			}
		}
	}
}

void deleteArray(int* ary[], int n)
{
	for (int i = 1; i <= n; ++i)
		delete[] ary[i];
}

int* myRealloc(int A[], int newSize)
{
	int* tmp = new int[newSize];

	while (--newSize >= 0)
	{
		tmp[newSize] = A[newSize];
	}
	delete[] A;
	A = tmp;
	return A;
}