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

vector<int>g[MAX_VERTICES + 1];
queue<int>q;
int dist[MAX_VERTICES + 1], n, m, source;

void readGraph() {
    int x, y;
    ifstream fin("bfs.in");
    fin >> n >> m >> source;
    //cout << n << " " << m << " " << source;
    for(int i = 1; i <= m; i++) {
        fin >> x >> y;
        //cout << x << " " << y << "\n";
        g[x].push_back(y);
    }
    fin.close();
}

void BFS(int source) {
    int node;
    for(int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    dist[source] = 0;
    q.push(source);
    while(!q.empty()) {
        node = q.front();
        for(auto i : g[node]) {
            if(dist[i] == -1) {
                dist[i] = 1 + dist[node];
                q.push(i);
            }
        }
        q.pop();
    }
}

void printDistances() {
    ofstream fout("bfs.out");
    for(int i = 1; i <= n; i++)
        fout << dist[i] << " ";
    fout << "\n";
    fout.close();
}

int main() {
    readGraph();
    BFS(source);
    printDistances();
    return 0;
}