/*
        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);
       }

}
void print()
{
    out=fopen("bfs.out","wt");
    int i;
    list<int>::iterator iterator_end;
    for(i=1;i<=varfuri;i++)
        fprintf(out,"%d ",vizitat.at(i)-1);

 /*   for(i=1;i<=varfuri;i++)
        if(!matrix[i].empty())
    {
        iterator_end = matrix[i].end();
        fprintf(out,"\nnodul %d -> ",i);

        for(list<int>::iterator it=matrix.at(i).begin();it!=iterator_end;++it)
            fprintf(out,"%d ",*it);
    }
*/
}

void BFS(int startNode)
{
    int nod_curent;
    coada.push_back(startNode);
    vizitat.at(startNode) = 1;
    while( coada.size() !=0)
    {
        nod_curent = coada.back();
        coada.pop_back();
        for(list<int>::iterator it=matrix.at(nod_curent).begin();it!=matrix.at(nod_curent).end();++it)
            if(!vizitat.at(*it))
            {
                coada.push_back(*it);
                vizitat.at(*it) = vizitat.at(nod_curent) + 1;
            }
    }

}