// Breadth First Search

#include <fstream>
#include <vector>
#define Nmax 100005
using namespace std;

int n, m, s, t = 1;
	
vector <int> lista[Nmax];
	
int coada[Nmax], cost[Nmax], dim[Nmax];


void bfs()
{
	memset(cost, -1, sizeof(cost));
	
	int t = 1;
	
	coada[t] = s;
	cost[s] = 0;
	
	for(int i = 1; i <= t; ++i)
	{
		for(int j = 0; j < dim[coada[i]]; ++j)
			
			if(cost[lista[coada[i]][j]] == -1)
			{
				
				coada[++t] = lista[coada[i]][j];
				cost[coada[t]] = cost[coada[i]] + 1;
				
			}
	}
	
	
}

int main()
{
	
	ifstream f("bfs.in");
	ofstream g("bfs.out");
	
	f >> n >> m >> s;

	
	for(int i = 1; i <= m; ++i)
	{
		int x, y;
		
		f >> x >> y;
		
		lista[x].push_back(y);
		
	}
	
	for(int i = 1; i <= n; ++i)
		dim[i] = lista[i].size();
	
	bfs();
	
	for(int i = 1; i <= n; ++i)
		g << cost[i] << " ";
	
	f.close();
	g.close();
	
	return 0;
}