#include<stdio.h>
#include<vector>   
using namespace std;   
#define nmax 100010
int n,m,st,l;   
vector <int> a[nmax];   
int g[nmax],s[nmax],c[nmax];   
void BF(int);   
int main(){   
    int i,x,y;
    freopen("bfs.in","r",stdin);   
    freopen("bfs.out","w",stdout);   
    scanf("%d %d %d",&n,&m,&st);   
    for(i=1;i<=m;i++){  
   
        scanf("%d %d",&x,&y);   
        a[x].push_back(y);   
    }   
    for(i=1;i<=n;i++)   
        g[i]=a[i].size();   
    BF(st);   
    for(i=1;i<=n;i++)   
        printf("%d ",c[i]);   
    printf("\n");   
    return 0;   
}   
void BF(int t){
    int i,j;   
    memset(c, -1 ,sizeof(c));   
    l=1;   
    c[t]=0;   
    s[l]=t;   
    for(i=1;i<=l;i++)   
        for(j=0;j<=g[s[i]];j++)   
            if(c[a[s[i]][j]]==-1){ 
  
		s[++l]=a[s[i]][j];
                c[s[l]]=c[s[i]]+1;   
            }   
}