#include<fstream> 
#include<vector> 
#define MAXN 100009;
using namespace std; 
int n, m, s; 
vector <int> Lista[MAXN]; 
int coada[MAXN], cost[MAXN]; 
bool viz[MAXN]; 
int prim, ultim; 
int main() 
{ 
int i, x, y, s; 
vector <int> :: iterator vec; 
ifstream f("bfs.in"); 
f>>n>>m>>s; 
memset(cost,-1,sizeof(cost)); 
for(i=0;i<m;++i) 
{
f>>x>>y; 
Lista[x].push_back(y); 
} 
f.close(); 
coada[ ultim ++ ] = s; 
cost[s] = 0; 
viz[s] = true; 
while ( prim <= ultim ) 
{ 
for( vec=Lista[coada[prim]].begin(); vec != Lista[coada[prim]].end(); ++vec ) 
{ 
if(!viz[*vec]) 
{ 
coada[ultim++]=*vec; 
cost[*vec]=cost[coada[prim]]+1; 
viz[*vec]=true; 
} 
} 
++prim; 
} 
ofstream g("bfs.out"); 
for( i=1; i<=n;i++ ) 
g<<cost[i]<<' '; 
g<<'\n'; 
g.close(); 
return 0; 
}