#include <iostream>
#include <fstream>
using namespace std;

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

const int dmax = 100010;

int vf[2*dmax];
int lst[dmax];
int urm[2*dmax];
int nr;

int C[dmax];
int cost[dmax];

int N, M, S;

void adauga(int x, int y)
{
    // ADAUGA IN LISTA LUI x PE y

    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void read()
{
    int x, y;

    in >> N >> M >> S;

    for(int i = 1; i <= M; i++)
    {
        in >> x >> y;
        adauga(x,y);
    }
}

void solve()
{
    int first, last;

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

    // ADAUG IN COADA NODUL S

    first = last = 1;

    C[1] = S;
    cost[S] = 0;

    while(first <= last)
    {
        int x = C[first];

        // PARCURG LISTA VECINILOR LUI x

        int p = lst[x];

        while(p)
        {
            int y = vf[p];

            if(cost[y] == -1)
            {
                last++;
                C[last] = y;
                cost[y] = 1 + cost[x];
            }

            p = urm[p];
        }

        first++;
    }
}

void write()
{
    for(int i = 1; i <= N; i++) out << cost[i] << " ";
}

int main()
{
    read();
    solve();
    write();

    return 0;
}