#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;

deque <int> coada;
int sol[100001],n,m,s,viz[100001];

struct nod {
    int x;
    nod *urm;
} *v[100001];

void adaugare(int x, int y) {//adaug varful y la varful x
    nod *p;
    p=new nod;
    p->x=y;
    p->urm=v[x];
    v[x]=p;
}

void bfs(int dc) {
    nod *p;
    for( ;coada.size(); ) {
        for(p=v[coada.front()]; p!=NULL; p=p->urm) {
            if(!viz[p->x]) {
                coada.push_back(p->x);
                sol[p->x]=sol[coada.front()]+1;
                viz[p->x]=1;
            }
        }
        viz[coada.front()]=1;
        coada.pop_front();
    }
}

void afisare() {
    nod *p;
    int k;
    for(k=1; k<=n; k++) {
        p=v[k];
        printf("%d:",k);
        while(p) {
            printf("%d ",p->x);
            p=p->urm;
        }
        printf("\n");
    }
}
int main()
{
    int i,x,y;
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    memset(sol,-1,sizeof(sol));
    scanf("%d %d %d",&n, &m, &s);
    for(i=0; i<m; i++) {
        scanf("%d %d", &x, &y);
        if(x!=y)
            adaugare(x,y);
    }
    //afisare();
    coada.push_back(s);
    sol[s]=0;
    viz[s]=1;
    bfs(s);
    for(i=1; i<=n; i++) printf("%d ", sol[i]);
    return 0;
}