#include <bits/stdc++.h>

#define MaximumEdges 1000000
#define MaximumNodes 100000

std::ifstream InFile("dfs.in");
std::ofstream OutFile("dfs.out");


int N, M, S;
// Assuming the data file won't have duplicate entries we can use a list
std::list <int> Adj[MaximumNodes];
int NArcs[MaximumNodes];
bool Seen[MaximumNodes];

std::queue <int> BFSQueue;
void BFS(int StartingIndex) {
    BFSQueue.push(StartingIndex);
    Seen[StartingIndex] = 1;

    NArcs[StartingIndex] = 0;

    int Index, Cost;
    while(!BFSQueue.empty()) {
        Index = BFSQueue.front();
        BFSQueue.pop();

        Cost = NArcs[Index];

        for (auto Node : Adj[Index]) {
            if(Seen[Node]);
            else {
                BFSQueue.push(Node);
                Seen[Node] = 1;

                NArcs[Node] = Cost + 1;
            }
        }
    }
}

void InitialiseData() {
    for (int i=0; i<N; i++)
        NArcs[i] = -1;
}

void Citire() {
    InFile >> N >> M >> S;
    S--;

    for (int i=0, x, y; i<M; i++) {
        InFile >> x >> y;
        // Because I can
        x--, y--;
        Adj[x].push_front(y);
    }

    InFile.close();
}

void Rezolvare() {
    InitialiseData();

    BFS(S);

    for (int i=0; i<N; i++)
        OutFile << NArcs[i] << " ";
}

int main()
{
    Citire();
    Rezolvare();

    InFile.close();
    OutFile.close();

    return 0;
}