#include <iostream>
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
vector <int> lista[NMAX];
int n, m, dist[NMAX];

void BFS(int nod){

    int k = 0, viz[NMAX], i, S, len, q[NMAX];
    for(i = 1;i <= n; ++i){
        viz[i] = 0;
        dist[i] = -1;
    }

    ++k;
    S = nod;
    q[1] = S;
    dist[S] = 0;
    while(k){
        S = q[k];
        --k;
        viz[S] = 1;
        printf("%d ",S);
        len = lista[S].size();
        for(i = 0;i < len; ++i){
            if(viz[lista[S][i]] == 0){
                ++k;
                q[k] = lista[S][i];
                viz[lista[S][i]] = 1;
                dist[lista[S][i]] = dist[S] + 1;
            }
        }
    }
}

int main(){

    FILE *f, *g;
    f = fopen("bfs.in","r");
    g = fopen("bfs.out","w");
    int i, s, x, y;

    fscanf(f,"%d %d %d",&n,&m,&s);
    for(i = 1;i <= m; ++i){
        fscanf(f,"%d %d",&x,&y);
        lista[x].push_back(y);
    }

    BFS(s);
    for(i = 1;i <= n; ++i)
        fprintf(g,"%d ",dist[i]);





}