#include <iostream>
#include <fstream>

using namespace std;

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

int graf [100002][2002];
int coada[100002][2];
int drum[100002], viz[100002];
int n, m, s, p, u;

void BF ()
{
    coada[0][0] = s;
    coada[0][1] = 0;
    viz[s] = 1;
    while (p <= u)
    {
        drum[coada[p][0]] = coada[p][1];

        for (int i=1; i<=graf[coada[p][0]][0]; i++)
            if (viz[graf[coada[p][0]][i]] == 0)
            {
                u ++;
                coada[u][0] = graf[coada[p][0]][i];
                coada[u][1] = coada[p][1] + 1;
                viz[graf[coada[p][0]][i]] = 1;
            }
        p ++;
    }
}

void afisare ()
{
    for (int i=1; i<=n; i++)
    {
        if (drum[i] == 0 && i != s)
            g << -1 << ' ';
        else
            g << drum[i] << ' ';
    }
}

int main()
{
    f >> n >> m >> s;
    for (int i=0; i<m; i++)
    {
        int x, y;
        f >> x >> y;
        graf[x][0] ++;
        graf[x][graf[x][0]] = y;
    }

    BF();

    afisare();

    return 0;
}