///infoarena BFS

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

const int N_MAX = 100001;
int n, m, s;
int dist[N_MAX];

map<int, vector<int> > listaAdiacenta;
queue<int> Q;

void BFS(int nod){
    dist[nod] = 0;
    Q.push(nod);

    while(not Q.empty()){
        int nc = Q.front(); /// = nodCurent
        cout << nc << ' ';
        for(int vecin : listaAdiacenta[nc]){
            if(dist[vecin] == -1){
                Q.push(vecin);
                dist[vecin] = dist[nc] + 1;
            }
        }
        Q.pop();
    }
}

int main()
{
    f >> n >> m >> s;

    ///aflam dist minim de la nodul S la orice nod;

    for(int i = 1, n1, n2; i <= m; ++i){
        f >> n1 >> n2;
        listaAdiacenta[n1].push_back(n2);
    }

    for(int i = 1; i <= n; ++i)
        dist[i] = -1;

    BFS(s);

    for(int i = 1; i <= n; ++i)
        g << dist[i] << ' ';

    return 0;
}