#include <fstream>

using namespace std;

ifstream cin("bfs.in");
ofstream cout("bfs.out");

int n, m, st, a[9000][9000], viz[9000], d[9000], k=0, coad[9000], inc=0, sf=0;
int dr=0;
void latime(int nd){
	viz[nd]=1; ++k; ++inc;
	for(int i=1; i<=n; ++i){
		if( a[nd][i]==1 && viz[i]==0 ){
			coad[sf++]=i; d[i]=d[nd]+1;
		}
	}
	if(coad[inc]!=0) latime(coad[inc]);
}

int main(){

	cin>>n>>m>>st;
	
	while(m--){
		int x, y;
		cin>>x>>y;
		a[x][y]=1;
	}

	coad[sf++]=st; latime(coad[inc]);
		for(int i=1; i<=k; ++i) {
	if(d[i]==0 && i!=st) cout<<-1<<" ", ++k;
		else cout<<d[i]<<" ";

}



	

	return 0;
}