#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include <queue>
#include <fstream>
#include <limits>

std::ofstream g("bfs.out");

std::array<std::vector<int>, 100001> graph;
std::vector<bool> visited(100001, false);
std::vector<bool> isInQueue(100001, false);
std::vector<int> cost(100001, std::numeric_limits<int>::max());
std::queue<int> nextNodes;

int numNodes, numEdges, source;

void ReadGraph()
{
    std::ifstream f("bfs.in");

    f >> numNodes >> numEdges >> source;

    int node, neighbour;

    for(int i = 1; i <= numEdges; ++i) {
        f >> node >> neighbour;

        graph[node].emplace_back(neighbour);
    }
}

#define BFS_TRAVERSAL
//#define DFS_TRAVERSAL

#ifdef BFS_TRAVERSAL

void Traverse()
{
    nextNodes.emplace(source);
    isInQueue[source] = true;
    cost[source] = 0;

    while(!nextNodes.empty()) {
        const auto& currentNode = nextNodes.front();

        for(const auto& neighbour : graph[currentNode]) {
            if(cost[currentNode] + 1 < cost[neighbour]) {
                cost[neighbour] = cost[currentNode] + 1;
            }

            if(!visited[neighbour] && !isInQueue[neighbour]) {
                nextNodes.emplace(neighbour);
                isInQueue[neighbour] = true;
            }
        }

        visited[currentNode] = true;
        nextNodes.pop();
    }
}

#endif // BFS_TRAVERSAL

#ifdef DFS_TRAVERSAL

void Traverse(int source)
{
    for(const auto& neighbour : graph[source]) {
        if(!visited[neighbour]) {
            Traverse(neighbour);
            visited[neighbour] = true;
        }
    }
    std::cout << source << ' ';
}

#endif // DFS_TRAVERSAL

int main()
{
    ReadGraph();
    Traverse();

    for(int i = 1; i <= numNodes; ++i) {
        g << ((cost[i] == std::numeric_limits<int>::max()) ? -1 : cost[i]) << ' ';
    }

    return 0;
}