#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_N = 100002;

int N, M, S, x, y;
int D[MAX_N];
vector < int > v[MAX_N];
queue < int > Q;

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

    f >> N >> M >> S;
    for(int i = 1; i <= M; ++i)
    {
        f >> x >> y;
        v[x].push_back(y);
    }

    for(int i = 1; i <= N; ++i)
        D[i] = -1;
    D[S] = 0;
    Q.push(S);
    while(!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        for(int i = 0; i < v[now].size(); ++i)
            if(D[ v[now][i] ] == -1 || D[now] + 1 < D[ v[now][i] ])
            {
                D[ v[now][i] ] = D[now] + 1;
                Q.push(v[now][i]);
            }
    }

    for(int i = 1; i <= N; ++i)
        g << D[i] << " ";
    g << '\n';

    f.close();
    g.close();

    return 0;
}