/*
        PARCURGEREA BREADTH FIRST SEARCH
*/
#include<stdio.h>
#include<vector>
#include<list>
using namespace std;
FILE *in,*out;
vector < list<int> > matrix;
vector < int > vizitat;
vector < int > coada;

int varfuri,muchii,startNode;

void read();
void BFS(int startNode);
void print();


int main()
{
    read();
    BFS(startNode);
    print();
    return 0;
}

void read()
{
    int i,x,y;
    in=fopen("bfs.in","rt");
    fscanf(in,"%d%d%d",&varfuri,&muchii,&startNode);
    matrix.resize(varfuri+1);
    vizitat.resize(varfuri+1);
    for(i=1;i<=muchii;i++)
       {
            fscanf(in,"%d%d",&x,&y);
            if(x!=y)
                matrix.at(x).push_back(y);
       }
    fclose(in);
}
void print()
{
    out=fopen("bfs.out","wt");
    int i;
     for(i=1;i<=varfuri;i++)
        fprintf(out,"%d ",vizitat.at(i)-1);
    fclose(out);
}

void BFS(int startNode)
{
    int nod_curent,w=-1;
    coada.push_back(startNode);
    vizitat.at(startNode) = 1;
    w=0;
    while( w!=coada.size() )
    {

        nod_curent = coada.at(w);
        w++;
   //     coada.erase(coada.begin());
        list<int>:: iterator end_iterator = matrix.at(nod_curent).end();
        for(list<int>::iterator it=matrix.at(nod_curent).begin();it!=end_iterator;it++)
            if(!vizitat.at(*it))
            {
                coada.push_back(*it);
                vizitat.at(*it) = vizitat.at(nod_curent) + 1;
            }
    }

}