///BFS INFO1 11.13
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

void BFS(vector<list<int> >& adjList,
         vector<int>& distances, int source) {
    queue<int> mQueue;
    mQueue.push(source);
    distances[source] = 0;

    list<int>::iterator it;
    int current;
    while(!mQueue.empty()) {
        current = mQueue.front();
        mQueue.pop();

        for(it = adjList[current].begin(); it != adjList[current].end(); it++)
            if(distances[*it] == -1) {
                distances[*it] = distances[current] + 1;
                mQueue.push(*it);
            } else
                if(distances[*it] > distances[current] + 1) {
                    distances[*it] = distances[current] + 1;
                    mQueue.push(*it);
                }
    }
}

int main() {
    ifstream inStr("bfs.in");
    ofstream outStr("bfs.out");

    int N, M, source;
    inStr >> N >> M >> source; --source;

    vector<list<int> > adjList(N);
    vector<int> distances(N, -1);

    int from, to;
    for(int i=0; i<M; i++) {
        inStr >> from >> to;
        adjList[--from].push_back(--to);
    }

    BFS(adjList, distances, source);

    for(int i=0; i<N; i++)
        outStr << distances[i] << ' ';
    outStr << '\n';

    return 0;
}