#include <bits/stdc++.h>
#define Nmax 100009
using namespace std;

#define USE_FILES 1

#ifdef USE_FILES
ifstream fin("bfs.in");
ofstream fout("bfs.out");
#define cin fin
#define cout fout
#endif // USE_FILES

int n,m,x,y,start,d[Nmax];
vector <int> G[Nmax];
queue <int> Q;
bitset <Nmax> inQ;

void BFS(int source) {

    d[source]=1;

    Q.push(source);
    inQ[source]=1;

    while (!Q.empty()) {

        int aux=Q.front();
        Q.pop();
        inQ[aux]=0;

        for (auto x: G[aux])
            if (d[x] > d[aux]+1 || d[x]==0) {

                d[x]=d[aux]+1;

                if (!inQ[x]) {

                    Q.push(x);
                    inQ[x]=1;
                }
            }
    }
}

int main() {

    cin>>n>>m>>start;

    for (int i=1; i<=m; ++i) {

        cin>>x>>y;
        G[x].push_back(y);
    }

    BFS(start);

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

    for (int i=1; i<=n; ++i) cout<<d[i]<<' ';

    return 0;
}