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

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

int n, m, s;
vector<int> a[1000010];
int d[1000010];
queue<int> q;

void bfs(int nod) {
    q.push(nod);
    while(!q.empty()) {
        nod = q.front();
        q.pop();
        for(int i=0; i < a[nod].size(); i++) {
            if(d[a[nod][i]] > d[nod] + 1) {
                d[a[nod][i]] = d[nod] + 1;
                q.push(a[nod][i]);
            }
        }
    }
}

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

	for(int i=1; i<=n; i++)
		d[i] = 1999999999;
	
	d[s] = 1;
	bfs(s);
	for(int i=1; i<s; i++)
		if(d[i] == 1999999999)
			cout << "-1 ";
		else
			cout << d[i] - 1 << ' ';
	cout << "0 ";
	for(int i=s+1; i<=n; i++)
		if(d[i] == 1999999999)
			cout << "-1 ";
		else
			cout << d[i] - 1 << ' ';
	
	return 0;
}