#include <fstream>
#include <vector>
#include <algorithm>
 
 
class Graf
{
private:
    static constexpr int NMAX = 100009;
    const int N, M;
    std::vector<int> Adiacenta[NMAX];  // liste de adiacenta
 
public:
    Graf(int, int);
    void AdMuchie(int, int);
    void Bfs(int, int*);
 
    static constexpr int getNMAX() { return Graf::NMAX; }
};
 
Graf::Graf(int n, int m)
    : N(n), M(m)
{
}
 
void Graf::AdMuchie(int ini, int fin)
{
    Adiacenta[ini].push_back(fin);    
}
 
void Graf::Bfs(int S, int* nrArce)
{
    int coada[N], st = 0, dr = 0;
 
    for (int i = 1; i <= N; ++i)
        nrArce[i] = -1;
    nrArce[S] = 0;
    coada[st] = S;
    while (st <= dr)
    {
        int curent = coada[st++];
        for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
            if(nrArce[*it] == -1)
            {
                coada[++dr] = *it;
                nrArce[*it] = nrArce[curent] + 1;
            }
    }
}
 
int main()
{   
    std::ifstream f("bfs.in");
    std::ofstream g("bfs.out");
    int N, M, S;
    int nrArce[Graf::getNMAX()];

    f >> N >> M >> S;
    Graf graf(N, M);
    for (int x, y, i = 0; i < M; ++i)
    {
        f >> x >> y;
        graf.AdMuchie(x, y);
    }
 
    graf.Bfs(S, nrArce);
 
    for(int i = 1; i <= N; ++i)
        g << nrArce[i] << ' ';
 
    return 0;
}