#include<fstream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

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

const int N=100001;

vector<int> a[N];
vector<int> v(N,-1);

int n,s;

void bfs() {
	int x;
	deque <int> c;
	c.push_back(s);
	v[s]=0;
	while (!c.empty()) {
		x=c.front();
		c.pop_front();
		for (vector<int>::iterator i=a[x].begin(); i!=a[x].end(); i++)
			if (v[*i]==-1) {
				c.push_back(*i);
				v[*i]=1+v[x];
			}
	}
	for (int i=1; i<=n; i++) {
		cout<<v[i]<<' ';
	}
}

int main() {
	int x,y,m;
	cin>>n>>m>>s;
	while (m--) {
		cin>>x>>y;
		a[x].push_back(y);
	}
	bfs();
}