#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>

int main() {
    auto in = std::ifstream{"bfs.in"};

    auto adj_list = std::unordered_map<int, std::unordered_set<int>>{};
    int nodes{}, edges{}, root{};
    in >> nodes >> edges >> root;

    for (auto idx = 0; idx < edges; ++idx) {
        int first{}, second{};
        in >> first >> second;
        if (!adj_list.contains(first)) {
            adj_list.insert({first, {}});
        }
        if (!adj_list.contains(second)) {
            adj_list.insert({second, {}});
        }
        adj_list[first].insert(second);
    }
    in.close();

    auto distances = std::vector<int>{};
    for (auto _: adj_list) {
        distances.emplace_back(-1);
    }
    distances[root - 1] = 0;

    auto to_be_seen = std::queue<int>{};
    to_be_seen.push(root);

    while (!to_be_seen.empty()) {
        auto current = to_be_seen.front();
        to_be_seen.pop();

        for (auto neighbour: adj_list[current]) {
            if (distances[neighbour - 1] == -1) {
                to_be_seen.push(neighbour);
                distances[neighbour - 1] = distances[current - 1] + 1;
            }
        }
    }

    auto out = std::ofstream{"bfs.out"};
    for (auto dist: distances) {
        out << dist << " ";
    }
    out << "\n";
    out.close();

    return 0;
}