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


int n,m, s, viz[100005];

struct graf
{
    int x;
    graf *next;
} *L[100005];

void add(graf *&prim, int vc)
{
    graf *p = new graf;
    p -> x = vc;
    p->next = prim;
    prim = p;

}

void citire()
{
    freopen("bfs.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &s);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        add(L[a], b);

    }
    for(int i=1;i<=n;i++)
        viz[i] = -1;
}

void bfs()
{
    int p = 0,u =0, c[10000];
    c[0] = s;
    int nr = 1;
    viz[s] = 0;
    int l = u;
    while(p<=u)
    {
        int v = c[p];
        if(l < u)
            {
                nr++;
                l = u;
            }
        for(graf*q = L[v];q;q=q->next)
            if(viz[q->x] == -1)
            {
                u++;
                c[u] = q->x;
                viz[q->x] = nr;
            }
        p++;
    }

}

void afisare()
{
    freopen("bfs.out", "w", stdout);
    for(int i=1;i<=n;i++)
    {
        printf("%d ", viz[i]);
    }
}
int main()
{
    citire();
    bfs();
    afisare();

    return 0;
}