#include <bits/stdc++.h>

#ifdef ONLINE_JUDGE
#define in std::cin
#define out std::cout
#else
std::ifstream in("bfs.in");
std::ofstream out("bfs.out");
#endif

template<typename T, size_t N>
constexpr size_t length_of(T (&)[N]) { return N; }

template<int N, int E>
struct Graph {
    struct ListNode {
        int node;
        int next;
    } m_data[E + N] = {};
    int m_list_start[N] = {};
    int m_current_idx = 0;
    int get_list_start(int u) {
        if (!m_list_start[u]) m_list_start[u] = ++m_current_idx;
        return m_list_start[u];
    }
    void append(int u, int v) {
        u = get_list_start(u);
        if (!m_data[u].node) {
            m_data[u].node = v;
            return;
        }
        int tmp = m_data[u].next;
        m_data[u].next = ++m_current_idx;
        m_data[m_current_idx].node = v;
        m_data[m_current_idx].next = tmp;
    }
    void append_bi(int u, int v) {
        append(u, v);
        append(v, u);
    }
    struct Iterator {
        ListNode *m_data;
        int m_idx;
        operator bool() {
            return m_data[m_idx].node;
        }
        Iterator &operator++() {
            m_idx = m_data[m_idx].next;
            return *this;
        }
        int operator*() {
            return m_data[m_idx].node;
        }
    };
    Iterator operator[](int u) {
        return Iterator{m_data, get_list_start(u)};
    }
};

constexpr int N = 1e5 + 1;
constexpr int M = 1e6 + 1;
Graph<N, M> g;
int d[N];

void bfs(int s) {
    std::queue<int> q{{s}};
    d[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto it = g[u]; it; ++it) {
            int w = *it;
            if (d[w]) continue;
            d[w] = d[u] + 1;
            q.push(w);
        }
    }
}

int main() {
    int n;
    int m;
    int s;
    in >> n >> m >> s;
    for (int i = 0; i < m; ++i) {
        int u, v;
        in >> u >> v;
        g.append(u, v);
    }
    bfs(s);
    for (int u = 1; u <= n; ++u) {
        out << d[u] - 1 << ' ';
    }
}