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

using namespace std;

int main() {
    int n, m, source;
    
    std::fstream is;
    is.open ("bfs.in", std::fstream::in);

    std::fstream os;
    os.open("bfs.out", std::fstream::out);

    is>>n>>m>>source;

    vector<int> dist(n+1, -1);
    dist[source] = 0;
    vector<vector<int>> arcs(n+1);
    
    
    for(int i=0; i<=n; ++i) {
        int s, d;
        is>>s>>d;
        arcs[s].push_back(d);    
    }
    
    queue<int> q;
    q.push((source));
    
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        
        for(int i=0; i<arcs[current].size(); ++i) {
            int next = arcs[current][i];
            if (dist[next] == -1) {
                dist[next] = dist[current] + 1;
                q.push(next);
            }
        }        
    }
    
    
    for(int i=1; i<=n; ++i)
        os<<dist[i]<<" ";

    is.close();
    os.close();

    return 0;
}