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

const int kNmax = 100005, INF = 1e6;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	int source;
	vector<int> adj[kNmax];

	void read_input() {
		ifstream fin("bfs.in");
		fin >> n >> m >> source;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
			//adj[y].push_back(x);
		}
		fin.close();
	}
    void bfs(vector<int> &d) {
        for(int i = 1; i <= n; ++i) {
            d[i] = INF;
        }
        d[source] = 0;
        queue<int> q;
        q.push(source);
        while(!q.empty()) {
            int u = q.front();
            for(unsigned i = 0; i < adj[u].size(); ++i) {
                int v = adj[u][i];
                if(d[v] == INF) {
                    d[v] = 1 + d[u];
                    q.push(v);
                }
            }
            q.pop();
        }
        for(int i = 1; i <= n; ++i) {
            if(d[i] == INF) {
                d[i] = -1;
            }
        }
    }
	vector<int> get_result() {
		vector<int> d(n + 1);
		/*
		TODO: Faceti un BFS care sa construiasca in d valorile d[i] = numarul
		minim de muchii de parcurs de la nodul source la nodul i.
		d[source] = 0
		d[x] = -1 daca nu exista drum de la source la x.
		*******
		ATENTIE: nodurile sunt indexate de la 1 la n.
		*******
		*/
		bfs(d);
		return d;
	}

	void print_output(vector<int> result) {
		ofstream fout("bfs.out");
		for (int i = 1; i <= n; i++) {
			fout << result[i] << (i == n ? '\n' : ' ');
		}
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}