#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

int main()
{
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    int s, n, m;
    cin >> n >> m >> s;
    --s;
    vector<int> out[n + 1];
    vector<int> distance(n, -1);
    distance[s] = 0;
    for(int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        out[a].push_back(b);
    }

    queue<int> q;
    q.push(s);
    vector<int> v(n, 0);
    v[s] = 1;
    while(!q.empty())
    {
        int vertex1 = q.front();
        for(int i = 0; i < out[vertex1].size(); ++i)
        {
            int vertex2 = out[vertex1][i];
            if(!v[vertex2])
            {
                v[vertex2] = 1;
                q.push(vertex2);
                distance[vertex2] = distance[vertex1] + 1;
            }
        }
        q.pop();
    }

    for(int i = 0; i < n; ++i)
        cout << distance[i] << ' ';

    return 0;
}