#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int n, m, s, c[100000], cost[100000], p;
bool v[100000];
vector <int> a[100000];

int main(){
	int i, j, k;
	bool found;

	fstream f;
	f.open("bfs.in", ios_base::in);
	f >> n >> m >> s; s--;
	for (k=0; k<m; k++){
		f >> i >> j;
		i--; j--;
		a[i].push_back(j);
	}
	f.close();

	i=j=0; v[s]=true; cost[s]=0; c[0]=s; p=1;
	while (i<=j){
		v[c[i]]=true; found=false;
		for (k=0; k<int(a[c[i]].size()); k++)
			if (v[a[c[i]][k]]==false){
				c[++j]=a[c[i]][k];
				cost[a[c[i]][k]]=p;
				found=true;
			}
		if (found==true)
			p++;
		i++;
	}

	f.open("bfs.out", ios_base::out);
	for (i=0; i<n; i++)
		if (cost[i]==0 && i!=s)
			f << "-1 ";
		else if (cost[i]==0 && i==s)
			f << "0 ";
		else
			f << cost[i] << ' ';
	f << '\n';
	f.close();

	return 0;
}