#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100001

using namespace std;

ifstream in("bfs.in");
ofstream out("bfs.out");

vector < int > laturi[NMAX];
int Distanta[NMAX];
queue<int> tail;

int n,m,s;
void Citire()
{
in>>n>>m>>s;
for(int i=0;i<m;i++)
{
    int x,y;
    in>>x>>y;
    laturi[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
    Distanta[i] = -1;
}
}
int main()
{
Citire();

tail.push(s);
Distanta[s] = 0;

int nod,vecin;
while(!tail.empty())
{
    nod = tail.front();
    tail.pop();
    for(unsigned int i=0;i<laturi[nod].size();i++)
    {
        vecin =laturi[nod][i];
        if(Distanta[vecin] == -1){
            tail.push(vecin);
            Distanta[vecin] = Distanta[nod] + 1;
        }
    }
}
for(int i=1;i<=n;i++)
out<<Distanta[i]<<" ";
out<<"\n";

}