#include<fstream>
using namespace std;
ifstream in("bps.in");
ofstream out("bps.out");
int m,n,start,c[100001],viz[100001],d[100001],li=1,ls;
struct nod{
int info;
nod*next;
};

nod*la[100001];
void add(int x, int y){
nod*n=new(nod);
n->info=n;
n->next=la[x];
la[x]=n;
}
void citire(){
in>>n>>m>>start;
for(int i=1;i<=m;i++){
int x,y;
in>>x>>y;
add(x,y);
}
}
int c_vida(){
return li>ls;
}
void pune(int x){
c[++ls]=x;
}
void scoate(int &x){
x=c[li++];
}
void bf(int start){
pune(start);
viz[start]=1;
while(!c_vida()){
int x;
scoate(x);
nod*nc=la[x];
while(nc){
int y=nc->info;
if(!viz[y]){
pune(y);
viz[y]=1;
d[y]=d[x]+1;
nc=nc->next;}
}
}
}
int main(){
citire();
bf(start);
for(int i=1;i<=n;i++)
out<<d[i]<<" ";
return 0;
}