#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

int N, M, S, *a[100010], q[100010], pas[100010];
bool viz[100010];

inline void Read()
{
    ifstream f("bfs.in");
    f>>N>>M>>S;
    int x, y, i;
    for (i=1; i<=N; i++)
    {
        a[i] = (int *)realloc(a[i], sizeof(int));
        a[i][0] = 0;
    }
    for (i=1; i<=M; i++)
    {
        f>>x>>y;
        a[x][0]++;
        a[x] = (int *)realloc(a[x], (a[x][0] + 1) * sizeof(int));
        a[x][a[x][0]] = y;
    }
    f.close();
}

inline void BFS()
{
    int pr, ul, x, nrpas, i;
    pr = ul = 0;
    q[0] = S;
    for (i=1; i<=N; i++)
        pas[i] = 2000000000;
    pas[S] = 0;
    while (pr<=ul)
    {
        x = q[pr];
        pr++;
        nrpas = pas[x];
        viz[x] = true;
        for (i=1; i<=a[x][0]; i++)
            if (nrpas + 1 < pas[a[x][i]])
            {
                pas[a[x][i]] = nrpas + 1;
                ul++;
                q[ul] = a[x][i];
            }
    }
    for (i=1; i<=N; i++)
        if(pas[i] == 2000000000)
            if (i != S)
                pas[i] = -1;

}

inline void Write()
{
    ofstream g("bfs.out");
    int i;
    for (i=1; i<=N; i++)
        g<<pas[i]<<" ";
    g<<"\n";
    g.close();
}

int main()
{
    Read();
    BFS();
    Write();
    return 0;
}