#include <queue>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, m, s;
    ifstream f("bfs.in");
    f >> n >> m >> s;

    vector < int> v(n + 1, -1);
    vector <vector<int> > graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int a, b;
        f >> a >> b;
        graph[a].push_back(b);
    }

    queue <int > q;
    q.push(s);
    v[s] = 0;

    while(!q.empty()){
    	int a = q.front();
    	q.pop();
    	for (int& b : graph[a]) {
    		if(v[b] != -1){
    			continue;
    		}
    		v[b] = v[a] + 1;
    		q.push(b);
    	}

    }

    ofstream g("bfs.out");

    for (int i = 1; i <= n; ++i)
    {
    	g << v[i] << " ";
    }

    f.close();
    g.close()
 ;   return 0;
}