#include <stdio.h>
#include <cstring>
#include <bitset>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <deque>
#define nmax 100010
using namespace std;
struct lista { int m; lista *next; };
int n,m,k,x,i,y,d[nmax],fr[nmax];
queue <int> que;
lista *a,*t[nmax];
int main(){
freopen("bfs.in","r",stdin);
freopen("bfs.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for (i=1;i<=m;i++){
    scanf("%d%d",&x,&y);
    a=new lista; a->m=y; a->next=t[x]; t[x]=a;
}
memset(d,-1,sizeof(d));
que.push(k); fr[k]=1; d[k]=0;
while (!que.empty()){
    x=que.front(); que.pop(); a=t[x];
    while (a){
        if (fr[a->m]==0) { fr[a->m]=1; que.push(a->m);
            d[a->m]=d[x]+1;
        }
    a=a->next;
    }
}
for (i=1;i<=n;i++) printf("%d ",d[i]);
return 0;
}