#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

int n,m,i,j,nod1,nod2,distanta[100001],coada[100001],prim,ultim,start;
vector <int> arce[100001];

void BFS()
{
    int nod,vecin;
    while(prim<=ultim) //parcurg graful
    {
        nod=coada[prim]; //iau nodul curent
        for(i=0;i<arce[nod].size();i++) // parcurg in vectorul de arce al nodului
        {
            vecin=arce[nod][i]; //iau vecinul curent
            if(distanta[vecin]==-1) //daca inca nu i am gasit drum atribui distantei valoarea distantei nodului +1(de la acest arc)
            {
                distanta[vecin]=distanta[nod]+1;
                ultim++;
                coada[ultim]=vecin;
            }
        }
        prim++;
    }
}

int main()
{
    f>>n>>m>>start;
    for(i=1;i<=m;i++) //pun in vectorul de arce, arcele corespunzatoare fiecaruui nod
    {
        f>>nod1>>nod2;
        arce[nod1].push_back(nod2);
    }
    for(i=1;i<=n;i++)
        distanta[i]=-1; //initializez toate distantele cu -1
    distanta[start]=0; //distanta nodului de start este 0
    prim=1;
    ultim=1;
    coada[1]=start;  //pornesc din nodul de start
    BFS();
    for(i=1;i<=n;i++)
        g<<distanta[i]<<" "; //afisez distantele
    return 0;
}