#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("bfs.in" );
ofstream cout("bfs.out");

int s;
vector <vector <int> > a;
vector <int> d;

void read()
{
    int n, m;
    cin >> n >> m >> s;
    a.resize(n + 1);
    d.resize(n + 1);
    fill(d.begin(), d.end(), -1);
    d[s] = 0;

    for (int x, y, i = 0; i < m; i++)
    {
        cin >> x >> y;

        if (x != y)
            a[x].push_back(y);
    }
}

void solve()
{
    vector <int> x;
    x.push_back(s);

    for (int j = 0; j < x.size(); j++)
    {
        for (int q = x[j], i = 0; i < a[q].size(); i++)
        {
            if (d[ a[q][i] ] == -1 || d[ a[q][i] ] > d[q] + 1)
            {
                d[ a[q][i] ] = d[q] + 1;
                x.push_back(a[q][i]);
            }
        }
    }
}

int main()
{
    read();

    solve();

    for (int i = 1; i < d.size(); cout << d[i++] << ' ');

    return 0;
}