//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

class Graph {
private:
    struct Edge {
        int from, to;
        Edge() { }
        Edge(const int _from, const int _to) : from(_from), to(_to) { }
    };
    
    template<typename T>
    struct Range {
        struct Iterator {
            T& operator *() const { return *iter; }
            bool operator !=(const Iterator& rhs) const { return iter != rhs.iter; }
            void operator ++() { ++iter; }
            T* operator +(int i) const { return iter + i; }
            size_t operator -(const Iterator& rhs) const { return iter - rhs.iter; }
            T* iter;
        };
        
        Range(T* _first, T* _last) : first({_first}), last({_last}) { }
        T operator[] (const int i) { return *(first + i); }
        size_t size() const { return last - first; }
        Iterator& begin() { return first; }
        Iterator& end() { return last; }
        Iterator first, last;
    };
public:
    Range<int> operator [](int u) { 
        return Range<int>(&edges[offset[u]], &edges[offset[u + 1]]); 
    }
    
    Graph() = default;
    Graph(const int N, const int M=0) : n(N), offset(N + 1) {
        if (M > 0) { in.reserve(M); }
    } 
    
    void AddEdge(int x, int y) { in.emplace_back(x, y); }
    
    void Init() {
        edges.resize(in.size());
        for (auto&& e : in) { offset[e.from] += 1; }
        for (int i = 1; i <= n; i += 1) { 
            offset[i] += offset[i - 1]; 
        }
        for (auto&& e : in) { 
            edges[--offset[e.from]] = e.to; 
        }
        in.clear();
    }
private:    
    int n;
    vector<int> offset, edges;
    vector<Edge> in;
};

int main() {
    ifstream cin("bfs.in");
    ofstream cout("bfs.out");
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, m, s; cin >> n >> m >> s; s -= 1;
    Graph G(n, m);
    for (int i = 0; i < m; i += 1) {
        int x, y; cin >> x >> y; x -= 1; y -= 1;
        G.AddEdge(x, y);
    }
    G.Init();
    
    vector<int> que(n), dist(n);
    int q_start = 0, q_end = 1;
    que[0] = s;
    dist[s] = 1;
    while (q_start != q_end) {
        const int node = que[q_start++];
        for (auto&& son : G[node]) {
            if (dist[son] == 0) {
                dist[son] = dist[node] + 1;
                que[q_end++] = son;
            }
        }
    }
    
    for (auto&& res : dist) {
        cout << res - 1 << ' ';
    }
}