#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <set>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int n, m, s;
vector <int> Graph[100005];

void bfs(int nod)
{
    vector <int64_t> d(n + 1, INT64_MAX);
    set <pair<int64_t, int>> a;
    a.insert({0, s});
    d[s] = 0;
    while (!a.empty())
    {
        int nod = begin(a)->second;
        a.erase(begin(a));
        for (const auto& val : Graph[nod])
            if (d[val] > 1 + d[nod])
            {
                a.erase({d[val], val});
                d[val] = 1 + d[nod];
                a.insert({d[val], val});
            }
    }
    d.erase(d.begin());
    for (const auto& val : d)
        g << (val == INT64_MAX ? -1 : val) << " ";

}

int main()
{
    int x, y;
    f >> n >> m >> s;
    while(m--)
    {
        f >> x >> y;
        Graph[x].push_back(y);
    }
//    is.resize(n + 1);
    bfs(s);
}