#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
int M, N, S, C[100001];
vector<int> m[100001];
queue<int> Q;

int main()
{
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int i, j, k, nod;

    fin >> N >> M >> S;

    for (k = 0; k < M; k++)
    {
        fin >> i >> j;
        m[i].push_back(j);
    }

    for  (i = 1; i <= N; i++)
        C[i] = -1;
    Q.push(S);
    C[S] = 0;

    while (!Q.empty())
    {
        nod = Q.front();
        for (i = 0; i < m[nod].size(); i++)
        {
            if (C[m[nod][i]] == -1)
            {
                C[m[nod][i]] = C[nod] + 1;
                Q.push(m[nod][i]);
            }
        }
        Q.pop();
    }

    for (i = 1; i <= N; i++)
        fout << C[i] << " ";

    fin.close();
    fout.close();

    return 0;
}