#include<stdio.h>
	#include<vector>
	#define MAX 100000
	using namespace std;
	
	FILE *f , *g ;
	int n , m , s , cost[MAX] , st[MAX] , p , viz[MAX];
	vector<int> a[MAX];
	vector<int>::iterator it;
	
	void citire();
	void solve();
	void tipar();
	
	int main()
	{
		citire();
		solve();
		tipar();
		return 0;
	}
	
	void citire()
	{
		int x , y;
		f=fopen("bfs.in" , "r" );
		fscanf(f , "%d%d%d" , &n , &m , &s );
		for(int i = 1 ; i<= m ; ++i )
			fscanf(f , "%d%d" , &x , &y) , a[x].push_back(y);
		fclose(f);
	}
	
	void solve()
	{
		for( int i = 1 ; i<= n ; ++i )
			cost[i] = -1;
		cost[s] = 0;
		int ls , ld  , k ;
		ls = ld = k = viz[s] = 1;
		st[1] = s;
		while(ls <= ld )
		{
			++p;
			for(int i = ls ; i <= ld ; ++i )
				for(it = a[st[i]].begin(); it < a[st[i]].end(); ++it )
					if(!viz[*it])
					{
						st[++k] = *it;
						viz[*it] = 1;
						cost[*it] = p;
					}
			ls = ld+1;
			ld = k;
		}
	}
	
	void tipar()
	{
		g=fopen("bfs.out" , "w" );
		for( int i = 1 ; i<= n ; ++i )
			fprintf(g , "%d " , cost[i]);
		fclose(g);
	}