#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
int n,m,s;

vector<int> lista[100005],nod,viz;
void citire(){
    int x,y;
    scanf("%d%d%d",&n,&m,&s);
    //lista.resize(n,vector<int>);
    nod.resize(n+1,-1);
    viz.resize(n+1,0);
    nod[s]=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        lista[x].push_back(y);
    }

}

void bfs(){
    queue<int> coada;
    coada.push(s);
    viz[s]=1;
    while(!coada.empty()){
        for(std::vector<int>::iterator it=lista[coada.front()].begin();it!=lista[coada.front()].end();it++)
            if(!viz[(*it)]){
                coada.push(*it);
                viz[*it]=1;
                nod[*it]=nod[coada.front()]+1;
                }
        coada.pop();
    }

}

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    citire();
    bfs();
    for(std::vector<int>::iterator it=nod.begin()+1;it!=nod.end();it++)
        printf("%d ",*it);
    return 0;
}