#include <fstream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 100003;

int N, M, S, dist[MAXN];
vector < int > G[MAXN];
queue < int > q;

void readInput() {
    ifstream fin("bfs.in");

    fin >> N >> M >> S;
    for ( int i = 0; i < M; ++i ) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }

    dist[S] = 1;
    q.push(S);

    fin.close();
}

void BFS( ) {

    while ( !q.empty() ) {
        int currentNode = q.front();
        q.pop();

        vector < int > :: iterator it;
        for ( it = G[currentNode].begin(); it != G[currentNode].end(); it++ ) {
            if ( !dist[*it] ) {
                q.push(*it);
                dist[*it] = dist[currentNode] + 1;
            }
        }
    }
}

void writeSolution() {
    ofstream fout("bfs.out");

    for ( int i = 1; i <= N; ++i )
        fout << dist[i] - 1 << ' ';

    fout.close();
}

int main() {

    readInput();
    BFS();
    writeSolution();

    return 0;
}