#include <fstream>
#include <deque>
#include <algorithm>
#include <vector>

using namespace std;

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

int s;
vector <deque <unsigned short> > 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);

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

        if (count(a[x].begin(), a[x].end(), y) == 0 && x != y)
            a[x].push_back(y);
    }
}

void solve()
{
    deque <int> x;
    x.push_back(s);
    d[s] = 0;

    while (x.size() != 0)
    {
        for (int q = x[0], 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]);
        }
        x.pop_front();
    }
}

int main()
{
    read();

    solve();

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

    return 0;
}