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

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

queue<int> Q;
bool explorat[100005];
int d[100005];
vector<vector<int>> vecini;

int main() {
    int n, m, s;
    fin >> n >> m >> s;
    int a, b;
    vecini.resize(n + 1);
    while(m--) {
        fin >> a >> b;
        vecini[a].push_back(b);
    }
    cout << "start: " << s << endl;
    Q.push(s);
    d[s] = 0;
    explorat[s] = 1;
    while(!Q.empty()) {
        int x = Q.front();
        cout << "explorez " << x << endl;
        Q.pop();
        for (int k : vecini[x]) {
            if(!explorat[k] || d[k] > d[x] + 1)
            {
                cout << "  " << k << endl;
                explorat[k] = 1;
                d[k] = d[x] + 1;
                Q.push(k);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!explorat[i])
            fout << "-1 ";
        else
            fout << d[i] << ' ';
    }
    return 0;
}