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

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
        for(j=0;j<G[S[i]];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;
            }


}

int main()
{
    in=fopen("bfs.in","rt");
    out=fopen("bfs.out","wt");
    fscanf(in,"%d %d %d",&N,&M,&start);
    for(i=1;i<=M;i++)
    {
        fscanf(in,"%d %d",&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++)
        fprintf(out,"%d",Cost[i]);
    return 0;
}