#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <deque>

using namespace std;

vector <int> v[100000];
int         ok[100000];
deque <int> coada;

int main()
{
    FILE *fin, *fout;
    int n,m,i,j,start;
    fin=fopen("bfs.in","r");
    fout=fopen("bfs.out","w");
    fscanf(fin,"%d%d%d",&n,&m,&start);
    start--;
    for(m;m>0;m--){
        fscanf(fin,"%d%d",&i,&j);
        i--;
        j--;
        v[i].push_back(j);
    }
    ok[start]=1;
    coada.push_back(start);
    while(coada.size()>0){
        i=coada[0];
        for(j=0;j<v[i].size();j++){
            if(ok[v[i][j]]==0){
                coada.push_back(v[i][j]);
                ok[v[i][j]]=ok[i]+1;
            }
        }
        coada.pop_front();
    }
    for(i=0;i<n;i++){
        fprintf(fout,"%d ",ok[i]-1);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}