#include<fstream>
#include<vector>
#include<string.h>
#define NMAX 100002
using namespace std;
FILE *in,*out;
int N,M,start,x,y,i,j;
vector<int> A[NMAX];
int Cost[NMAX],S[NMAX];

void BFS(int nod);

int main()
{
    ifstream in("bfs.in");
    ofstream out("bfs.out");
    in>>N>>M>>start;
    for(i=1;i<=M;i++)
    {
        in>>x>>y;
        A[x].push_back(y);
    }
    /*for(i=1;i<=N;i++)
    {
        G[i]=A[i].size();
    }*/
    BFS(start);
    for(i=1;i<=N;i++)
        out<<Cost[i]<<" ";
    return 0;
}

void BFS(int nod)
{
    int L=1;
    memset(Cost, -1, sizeof(Cost));      // Marchez toate nodurile ca fiind nevizitate

    //  Introduc nodul de start in coada
    Cost[nod]=0;
    S[L]=nod;
    for(i=1;i<=L;i++)   //  Elimin pe rand nodurile din coada
    {
        int dim=A[S[i]].size();
        for(j=0;j<dim;j++)  //  Parcurg vecinii nodului ce urmeaza sa fie eliminat
            if(Cost[A[S[i]][j]]==-1)
            {
                //Adaug vecinii nevizitati in coada si le calculez distanta
                S[++L]=A[S[i]][j];
                Cost[S[L]]=Cost[S[i]]+1;
            }
    }

}