#include <fstream>
#include <vector>
#include <queue>

using namespace std ;
ifstream cin ("input") ;
ofstream cout ("output") ;

struct node {
    int neigh ;
    node *nxt ;
    node () {
        this -> neigh = 0 ;
        this -> nxt = NULL ;
    }
};

class Graph {
public:
    int n ;
    vector <node *> list ;
    Graph (int n) {
        this -> n = n ;
        list.resize (this -> n + 1) ;
        for (int i = 1 ; i <= this -> n ; ++ i) {
            list [i] = NULL ;
        }
    }
    void InsertEdge (int x, int y) {
        insertEdge(x, y);
    }
    void Write (int x) {
        write (x) ;
    }

private :
    void insertEdge (int x, int y) {
        node *newnode = new node () ;
        newnode -> neigh = y ;
        newnode -> nxt = list [x] ;
        list [x] = newnode ;
    }
    void write (int x) {
        for (node* i = list [x] ; i != NULL; i = i -> nxt) {
            cout << i -> neigh << ' ' ;
        }
        cout << endl ;
    }
};

int main () {
    int n, m, source;
    cin >> n >> m >> source ;
    Graph *G = new Graph (n) ;
    for (int i = 1 ; i <= m ; ++ i) {
        int x, y ;
        cin >> x >> y ;
        G -> InsertEdge(x, y) ;
    }
    vector <int> dist (n + 1, 1 << 30) ;
    dist [source] = 0 ;
    queue <int> Q ;
    Q.push(source) ;
    while (!Q.empty()) {
        auto cur = Q.front() ;
        Q.pop() ;
        for (node* i = G -> list [cur] ; i != NULL ; i = i -> nxt) {
            if (dist [i -> neigh] > dist [cur] + 1) {
                dist [i -> neigh] = dist [cur] + 1 ;
                Q.push(i -> neigh) ;
            }
        }
    }
    for (int i = 1 ; i <= n ; ++ i) {
        if (dist [i] == (1 << 30)) {
            cout << "-1 " ;
        }
        else {
            cout << dist [i] << ' ' ;
        }
    }
    return 0 ;
}