#include <stdio.h>
#include <vector>
#include <queue>
#include <bitset>
#define Nmax 100010

using namespace std;

int use[Nmax];
vector<int> A[Nmax];
queue<int> Q;
int n,m,s;

void read(){
	int i,x,y;
	freopen("bfs.in","r",stdin);
   freopen("bfs.out","w",stdout);
   scanf("%d%d%d",&n,&m,&s);
   for(i=1;i<=m;++i){
   	scanf("%d%d",&x,&y);
      A[x].push_back(y);
   }
}

void work(){
	int i,x;
   vector<int>::iterator it;
   Q.push(s); use[s]=1;
   while( !Q.empty() ){
   	x=Q.front();
      for(it=A[x].begin(); it!=A[x].end(); it++)
      	if(!use[*it]){
         	use[*it]=use[x]+1;
            Q.push(*it);
         }
      Q.pop();
   }
}

void write(){
	int i;
   for(i=1;i<=n;i++) printf("%d ",use[i]-1);
   fclose(stdin); fclose(stdout);
}

int main(){
	read();
   work();
   write();
   return 0;
}