#include <iostream>
#include <stdio.h>

using namespace std;

template <class T>
class Vector {
protected:
    T* theData;
    int theSize, Occupied;

public:
    Vector();
    virtual void pushBack(T element);
    virtual void popBack(){ Occupied--; }
    virtual int Vsize() { return Occupied; }
    virtual T operator[] (int x) { return theData[x];}
};

template <class T>
Vector<T> :: Vector(){
    theData = new T[1];
    theSize = 1024;
    Occupied = 0;
}

template <class T>
void Vector<T> :: pushBack(T element) {

    if(theSize == Occupied) {
        T* old = theData;

        theSize <<= 1;
        theData = new T[theSize];

        copy(old, old + Occupied, theData);
    }

    theData[Occupied++] = element;
}


template <class U>
class Queue : public Vector<U>{
public:
    void push(U elem) { this->pushBack(elem); }
    U pop() { this->popBack(); return this->theData[this->Occupied]; }
    bool isEmpty() { return this->Occupied == 0; }
};

const int nmax = 100010;
Vector<int> G[nmax];
int Seen[nmax];
Queue<int> Q;

int main()
{
    freopen ("bfs.in", "r", stdin);
    freopen ("bfs.out", "w", stdout);

    int N, M, S, i, node, x, y;

    cin >> N >> M >> S;
    while(M--) {
        cin >> x >> y;
        G[x].pushBack(y);
    }

    Q.push(S);
    Seen[S] = 1;
    while(!Q.isEmpty()) {
        node = Q.pop();
        for(i = 0; i < G[node].Vsize(); i++)
            if(Seen[G[node][i]] == 0) {
                Q.push(G[node][i]);
                Seen[G[node][i]] = Seen[node] + 1;
            }
    }

    for(i = 1; i <= N; i++)
        cout << Seen[i] - 1 << " ";
    return 0;
}