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


using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

void bf(int N, int M, int S, vector<vector<int>>& liste, vector<int>& vizitat, vector<int>& distante)
{
    queue<int> coada;
    coada.push(S);
    vizitat[S] = 1;
    distante[S] = 0;
    while (coada.size() != 0)
        {
            int i = coada.front();
            coada.pop();
            for(auto& a: liste[i])
            {
                if (vizitat[a] == 0)
                {
                    coada.push(a);
                    vizitat[a] = 1;
                    distante[a] = distante[i] + 1;

                }

            }


        }

}

int main()
{
    int N, M, S;
    vector<vector<int>> liste;
    vector<int> vizitat;
    vector<int> distante;
    fin>>N>>M>>S;
    liste.resize(N + 1);
    vizitat.resize(N + 1);
    distante.resize(N + 1);

    for (int i = 1; i <= M; i++)
    {
        int x, y;
        fin>>x>>y;
        liste[x].push_back(y);
    }

    for (int i = 1; i <= N; i++)
        distante[i] = -1;

    bf(N, M, S, liste, vizitat, distante);

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

    return 0;
}