#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int main()
{
    int n, m, s;
    fin>> n >> m >> s;

    vector<int> p[n + 1];

    vector<int> res(n + 1, -1);
    for(int i = 0 ; i < m; i++) {
        int x, y;
        fin >> x >> y;
        p[x].push_back(y);
    }

    res[s] = 0;
    queue<int> q;

    q.push(s);

    while(!q.empty()) {
        int x = q.front();

        for(int aux:p[x]) {
            res[aux] = res[x] + 1;
            q.push(aux);
        }
    }

    for(int i:res) {
        fout << i << " ";
    }
    return 0;
}