#include <fstream>
#include <vector>
#include <string.h>

#define max_n 100001

using namespace std;

int i,n,m,s,x,y,st,dr;
bool u[max_n];
int c[max_n],d[max_n];
vector <int> g[max_n];
vector <int>::iterator it;

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

void BF(int s) {
	memset(u,false,sizeof(u));
	memset(d,-1,sizeof(d));
	st=dr=1;
	c[1]=s;
	u[s]=true;
	d[s]=0;
	for (; st<=dr; st++) {
		x=c[st];
		for (it=g[x].begin(); it!=g[x].end(); it++) 
			if (!u[*it]) {
				c[++dr]=*it;
				u[*it]=true;
				d[*it]=d[x]+1;
			}
	}
}
	
	

int main () {
	in >> n >> m >> s;
	for (i=1; i<=m; i++) {
		in >> x >> y;
		g[x].push_back(y);
	}
	
	BF(s);
	for (i=1; i<n; i++) 
		out << d[i] << ' ';
	out << d[n] << '\n';
	return 0;
}