#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int N,S;
long M;
vector < vector <int> > Graf;
vector <int> Viz,Dist;
void Citire()
{
ifstream f ("bfs.in");
f>>N>>M>>S;
Graf.resize(N);
Viz.resize(N,0);
Dist.resize(N,-1);
for (int i=0;i<M;i++)
{
int x,y;
f>>x>>y;
x--;y--;
Graf[x].push_back(y);
//Graf[y].push_back(x);
}
}
void BFS (int n)
{
int i,j;
vector <int> Coada;
Coada.push_back(n);
Dist[n]=0;
Viz[n]=1;
i=j=0;
while (i<=j)
{
for (int k=0;k<Graf[Coada[i]].size();k++)
if (Viz[Graf[Coada[i]][k]]==0)
{
//cout<<i+1<<" "<<Graf[Coada[i]][k]+1<<endl;
Coada.push_back(Graf[Coada[i]][k]);
Dist[Graf[Coada[i]][k]]=Dist[Coada[i]]+1;
Viz[Graf[Coada[i]][k]]=1;
j++;
}
i++;
}
}
int main()
{
Citire();
BFS(S-1);
ofstream g ("bfs.out");
for (int i=0;i<N;i++)
{
g<<Dist[i]<<" ";
}
g.close();
return 0;
}