#include <bits/stdc++.h>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n, m, start, d[100100];
bitset<100100> reached;
vector<int> edges[100100];
 
int main() {
    fin >> n >> m >> start;
    for (int i = 1; i <= m; i++) {
		int a, b;
        fin >> a >> b;
        edges[a].push_back(b);
    }
 
    for (int i = 1; i <= n; i++)
        d[i] = -1;
    d[start] = 0;
    
	queue<int> c;
    c.push(start);
    reached[start] = true;
 
    while (!c.empty()) {
        int act = c.front();
        c.pop();
        
        for (int i = 0; i < edges[act].size(); i++) {
			int to = edges[act][i];
            if (!reached[to]) {
                reached[to] = true;
                d[to] = d[act] + 1;
                c.push(to);
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
        fout << d[i] << ' ';
    return 0;
}