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

using namespace std;

vector<vector<int>> graph;
vector<int> distances;

void bfs(const int s)
{
    distances[s] = 0;
    queue<int> node_queue;
    node_queue.push(s);

    while (!node_queue.empty())
    {
        const auto node = node_queue.front();
        node_queue.pop();

        const auto dist = distances[node];

        for (auto neighbor : graph[node])
        {
            if (distances[neighbor] == -1)
            {
                distances[neighbor] = dist + 1;
                node_queue.push(neighbor);
            }
        }
    }
}

int main()
{
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int n, m, s;

    fin >> n >> m >> s;
    s--;
    graph = vector<vector<int>>(n, vector<int>());
    distances = vector<int>(n, -1);

    for (auto i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
    }

    fin.close();

    bfs(s);
    for (auto dist : distances)
        fout << dist << " ";

    fout.close();

    return 0;
}