#include <fstream>
#include <iostream>
#include <vector>
#define NMAX 1000005
using namespace std;
vector <int> v[NMAX];
int dist[NMAX] = {-1}, C[NMAX], nrVec[NMAX];

void BFS(int start){
    int p = 1;
    int u = 1;
    C[1] = start;
    dist[start] = 0;
    //int length = 1;
    //simulam coada
    while(p <= u){
        int nod_curent = C[p++];
        for(int i = 0; i < nrVec[nod_curent]; ++i){
            if(dist[v[nod_curent][i]] == -1){
                C[++u] = v[nod_curent][i];
                dist[C[u]] = dist[nod_curent] + 1;
            }
        }
    }
}
int main()
{
    ifstream f("bfs.in");
    int n, m, start;
    f >> n >> m >> start;
    while(m){
        int a, b;
        f >> a >> b;
        v[a].push_back(b);
        m--;
    }
    f.close();

    for (int i = 1; i <= n; ++i){
        nrVec[i] = v[i].size();
        dist[i] = -1;
    }
    BFS(start);

    ofstream g("bfs.out");
    for(int i = 1; i <= n; ++i){
        g << dist[i] << " ";
    }
    g.close();
    return 0;
}