// https://www.infoarena.ro/problema/bfs - Szucs Patrik - Kevin
#include <fstream>
#include <queue>
#include <vector>

void bfs(std::queue<int> &sor, std::vector<std::vector<int>> &graf, std::vector<int> &indx)
{
    while (!sor.empty())
    {
        int curr = sor.front(); // utoljara berakott elem - 1
        sor.pop();
        for (int i : graf[curr])
        {
            if (indx[i] == -1)
            {
                indx[i] = indx[curr] + 1;
                sor.push(i);
            }
        }
    }

    return;
}

int main()
{
    int n, m, s;

    std::ifstream in("bfs.in");
    in >> n >> m >> s;

    std::vector<std::vector<int>> graf(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        in >> a >> b;

        graf[a - 1].push_back(b - 1);
    }
    in.close();

    std::queue<int> sor;
    std::vector<int> indx(n, -1);

    sor.push(s - 1);
    indx[s - 1] = 0;

    bfs(sor, graf, indx);

    std::ofstream out("bfs.out");
    for (auto &elem : indx)
        out << elem << " ";

    out.close();
    return 0;
}