//Ex1: a)https://infoarena.ro/problema/bfs
//Se considera un graf orientat cu N varfuri si M arce. 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.
//Date de intare: Fisierul de intrare bfs.in contine pe prima linie 3 numere intregi N M S, cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x y, cu semnificatia ca exista arc orientat de la x la y.
//Date de iesire: In fisierul de iesire bfs.out se vor afla N numere separate prin spatiu cu semnificatia ca al i-lea numar reprezinta numarul minim de arce ce trebuie parcurse de la nodul S la nodul i.

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <list>

using namespace std; 

ifstream fin("bfs.in"); 
ofstream fout("bfs.out");

int main()
{
	int nrNoduri, nrArce, nodPornire; 
	fin >> nrNoduri >> nrArce >> nodPornire; 

	//citire si memorare graf 
	vector<list<int>>listeAdiacenta; 
	for (int nod = 0; nod <= nrNoduri; nod++)
	{
		list<int> listaVida; 
		listeAdiacenta.push_back(listaVida); 
	}

	for (int i = 1; i <= nrArce; i++)
	{
		int nodIntrare, nodIesire; 
		fin >> nodIntrare >> nodIesire; 

		if (nodIntrare != nodIesire)
		{
			listeAdiacenta[nodIntrare].push_back(nodIesire);
			listeAdiacenta[nodIntrare].sort();
			listeAdiacenta[nodIntrare].unique();
		}
	}
   
	vector<int> distanta; 
	for (int i = 0; i <= nrNoduri; i++)
		distanta.push_back(0); 

	queue<int> vecini;
	vecini.push(nodPornire); 
	while (!vecini.empty())
	{
		for (auto adrElement = listeAdiacenta[vecini.front()].begin(); adrElement != listeAdiacenta[vecini.front()].end(); adrElement++)
		{
			int element = *adrElement;
			if (distanta[element] == 0)
			{
				vecini.push(element);
				distanta[element] = distanta[vecini.front()] + 1; 
			}
		}

		vecini.pop(); 
	}

	for (int nod = 1; nod <= nrNoduri; nod++)
	{
		if (nod == nodPornire)
			fout << "0 ";
		else
		{
			if (distanta[nod] == 0)
				fout << "-1 ";
			else
				fout << distanta[nod] << " ";
		}
	}

}